9 ms·

I can't help but notice how this code, as well as in the article, there's no checks for a) a NULL list or b) that the item is in fact part of the list. A simple

I can't help but notice how this code, as well as in the article, there's no checks for a) a NULL list or b) that the item is in fact part of the list. A simple fix is: while (!!walk && walk != entry) { prev = walk; walk = walk->next; } or while (!!indirect && !!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; ...because without those checks it's pretty easy to see where you'll crash... but by putting in those checks, perhaps the second method might actually be less 'elegant'. Edit: did I miss something? Re-checking this, the second method will still crash if/when next is NULL (because you can't get the address of NULL), which means the 'elegant' seems to be a quagmire of lurking faults.

mjevans 6y ago
I believe the implicit requirement is that the item is known to exist within the list. With that requirement in place the extra guards aren't requisite (they're implicit) and in kernel code this probably offers a performance edge and is a reasonable requirement. Either having an implementation that has an extra check once at the end of the list, or that verifies the presence of the item and passes that node through to a deletion subroutine, would be good alternatives but still utilize the same pointer to structure view.
- shallowthought 6y ago
  That's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.
  - cmroanirgo 6y ago
    This is why Linus' code shouldn't be copied verbatim and used in the real world. The Kernel is an extremely isolated and contained system. At the very least, the code should add comments on the the assumptions that are vital...otherwise n00bs will copy the code as gospel and run into all sorts of problems.
    - ggrrhh_ta 6y ago
      The actual code in the kernel is well documented (and different, lines 103-149): https://github.com/torvalds/linux/blob/master/include/linux/list.h https://github.com/torvalds/linux/blob/master/include/linux/...
  - axaxs 6y ago
    Simply put, safety slows code down. It's a matter of whether you know what's happening underneath or not. The more you try to make C completely safe, the more you slow it down and therefore remove the need to have written it in C in the first place. Whether that's a good thing or not is an exercise for the implementer.
    - inglor_cz 6y ago
      True, but costs of comparison to NULL aren't massive. It is one of the fastest things out there. It was my experience when tuning a linear algebra library (just for internal use) that such comparisons are almost unobservable in total performance tests.
      - atq2119 6y ago
        If you're writing a linear algebra library, then the bulk of executing code should be floating point vector operations in tight loops with known bounds. A NULL pointer check in the prolog where you set up the loop is going to be negligible. This is very different from kernel code, which by its nature isn't very computational but doing resource management all day long and pretty much all it does is stuff that looks like walking linked lists.
        inglor_cz 6y ago
        That was a very specific linear algebra, we toyed around with huge but sparse matrices. Not anything graphics-related, rather number theory-related. But there was a lot of integer comparisons in there. This was around 2001-2002 anyway. Things might have changed.
      - scoutt 6y ago
        > costs of comparison to NULL aren't massive Depends on how often you are doing the comparison. Is it 1 time/second, or 10 million times a second? There is a difference. If the code above is the one in charge of putting/removing network packets in a queue, or putting threads ordered by priority for the scheduler, then you should consider the side effects of checking for NULL. If you are going to implement this function in a library for Jimmy The Programmer[1], then check for NULL. [1] https://blog.codinghorror.com/new-programming-jargon/ https://blog.codinghorror.com/new-programming-jargon/
kbumsik 6y ago
You don't need to check !!indirect. There is no cases that the indirect pointer is NULL: while (!!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; Also I would rather use * indirect instead of !!(* indirect).
- cmroanirgo 6y ago
  correct. I was just being overly pedantic
  - muro 6y ago
    Why the !! ? I thought that only makes sense in JS.
    - cmroanirgo 6y ago
      I'm not sure about the current state of compiler optimisations, but IIRC in the olde-days, a not not in an if() statement would assemble to JZ, saving a clock cycle (& an opcode?), and wouldn't need to stall to load in the full width of the register. Today's branch predicting compilers are beyond me. I still use it as a clarification that it's a deliberate boolean operation, rather than implicit.
      - user-the-name 6y ago
        I highly doubt that any modern compiler would generate different code with or without the !!. Not even sure why an old compiler would do that? It's the exact same semantics, surely.
    - nitrogen 6y ago
      I thought that only makes sense in JS. In C any nonzero value is considered "truthy", and on most architectures NULL is defined to be (void * )(0) or similar. The logical not operator AKA bang operator will replace truthiness with 0, and falsiness with 1. So applying it twice collapses all nonzero values to 1.
yarcob 6y ago
That code is not a general purpose library function; it assumes the element exists. If you call that method and the element doesn't exist, presumably something has gone wrong already. Adding a NULL pointer check is not going to fix it. You just silently ignore the error. You'll prevent the crash, but there's no mechanism for handling the error.
- adrianN 6y ago
  And instead of adding a check and crashing visibly here you wait even longer until your program misbehaves due to the error? The longer the program runs after something went wrong, the harder it is to debug, and the more likely it becomes that you get an exploitable bug.
  - larsrc 6y ago
    Are you arguing that we should leave known crash bugs in the code?
    - aidos 6y ago
      It’s not a bug, in this case. It depends on the behaviour the library is specified to handle, but if you ask me to remove a specific item from a list, and that item isn’t in the list, what should I do? I can fail so you can catch it, or if you don’t catch it, you’ll at least see exactly what went wrong. You expected the item to be in the list and it wasn’t. Your preconditions were wrong from the beginning and you have an (unknown) bug in the code. The alternative is that I can’t find the item and I silently suck it up and don’t notify you. If that’s the api we’ve all agreed on, that’s fine. It was on you to check for the thing in the list first and then remove it. But it’s a bit weird if you think about it - now you need to traverse the list twice. Once to check for the existence (and fail out yourself) and once to remove.
      - christophilus 6y ago
        I think a better approach is to return a bool or something like that, rather than crashing. But I agree that silently handling this case is the worst of the options.

mjevans 6y ago

I believe the implicit requirement is that the item is known to exist within the list. With that requirement in place the extra guards aren't requisite (they're implicit) and in kernel code this probably offers a performance edge and is a reasonable requirement. Either having an implementation that has an extra check once at the end of the list, or that verifies the presence of the item and passes that node through to a deletion subroutine, would be good alternatives but still utilize the same pointer to structure view.

shallowthought 6y ago
That's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.
- cmroanirgo 6y ago
  This is why Linus' code shouldn't be copied verbatim and used in the real world. The Kernel is an extremely isolated and contained system. At the very least, the code should add comments on the the assumptions that are vital...otherwise n00bs will copy the code as gospel and run into all sorts of problems.
  - ggrrhh_ta 6y ago
    The actual code in the kernel is well documented (and different, lines 103-149): https://github.com/torvalds/linux/blob/master/include/linux/list.h https://github.com/torvalds/linux/blob/master/include/linux/...
- axaxs 6y ago
  Simply put, safety slows code down. It's a matter of whether you know what's happening underneath or not. The more you try to make C completely safe, the more you slow it down and therefore remove the need to have written it in C in the first place. Whether that's a good thing or not is an exercise for the implementer.
  - inglor_cz 6y ago
    True, but costs of comparison to NULL aren't massive. It is one of the fastest things out there. It was my experience when tuning a linear algebra library (just for internal use) that such comparisons are almost unobservable in total performance tests.
    - atq2119 6y ago
      If you're writing a linear algebra library, then the bulk of executing code should be floating point vector operations in tight loops with known bounds. A NULL pointer check in the prolog where you set up the loop is going to be negligible. This is very different from kernel code, which by its nature isn't very computational but doing resource management all day long and pretty much all it does is stuff that looks like walking linked lists.
      - inglor_cz 6y ago
        That was a very specific linear algebra, we toyed around with huge but sparse matrices. Not anything graphics-related, rather number theory-related. But there was a lot of integer comparisons in there. This was around 2001-2002 anyway. Things might have changed.
    - scoutt 6y ago
      > costs of comparison to NULL aren't massive Depends on how often you are doing the comparison. Is it 1 time/second, or 10 million times a second? There is a difference. If the code above is the one in charge of putting/removing network packets in a queue, or putting threads ordered by priority for the scheduler, then you should consider the side effects of checking for NULL. If you are going to implement this function in a library for Jimmy The Programmer[1], then check for NULL. [1] https://blog.codinghorror.com/new-programming-jargon/ https://blog.codinghorror.com/new-programming-jargon/

kbumsik 6y ago

You don't need to check !!indirect. There is no cases that the indirect pointer is NULL: while (!!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; Also I would rather use * indirect instead of !!(* indirect).

cmroanirgo 6y ago
correct. I was just being overly pedantic
- muro 6y ago
  Why the !! ? I thought that only makes sense in JS.
  - cmroanirgo 6y ago
    I'm not sure about the current state of compiler optimisations, but IIRC in the olde-days, a not not in an if() statement would assemble to JZ, saving a clock cycle (& an opcode?), and wouldn't need to stall to load in the full width of the register. Today's branch predicting compilers are beyond me. I still use it as a clarification that it's a deliberate boolean operation, rather than implicit.
    - user-the-name 6y ago
      I highly doubt that any modern compiler would generate different code with or without the !!. Not even sure why an old compiler would do that? It's the exact same semantics, surely.
  - nitrogen 6y ago
    I thought that only makes sense in JS. In C any nonzero value is considered "truthy", and on most architectures NULL is defined to be (void * )(0) or similar. The logical not operator AKA bang operator will replace truthiness with 0, and falsiness with 1. So applying it twice collapses all nonzero values to 1.

yarcob 6y ago

That code is not a general purpose library function; it assumes the element exists. If you call that method and the element doesn't exist, presumably something has gone wrong already. Adding a NULL pointer check is not going to fix it. You just silently ignore the error. You'll prevent the crash, but there's no mechanism for handling the error.

adrianN 6y ago
And instead of adding a check and crashing visibly here you wait even longer until your program misbehaves due to the error? The longer the program runs after something went wrong, the harder it is to debug, and the more likely it becomes that you get an exploitable bug.
- larsrc 6y ago
  Are you arguing that we should leave known crash bugs in the code?
  - aidos 6y ago
    It’s not a bug, in this case. It depends on the behaviour the library is specified to handle, but if you ask me to remove a specific item from a list, and that item isn’t in the list, what should I do? I can fail so you can catch it, or if you don’t catch it, you’ll at least see exactly what went wrong. You expected the item to be in the list and it wasn’t. Your preconditions were wrong from the beginning and you have an (unknown) bug in the code. The alternative is that I can’t find the item and I silently suck it up and don’t notify you. If that’s the api we’ve all agreed on, that’s fine. It was on you to check for the thing in the list first and then remove it. But it’s a bit weird if you think about it - now you need to traverse the list twice. Once to check for the existence (and fail out yourself) and once to remove.
    - christophilus 6y ago
      I think a better approach is to return a bool or something like that, rather than crashing. But I agree that silently handling this case is the worst of the options.