DOUBLE DELETE with "DL_DELETE2" create BROKEN list:

[aotto1968]

Hi, I investigate an BUG in my code end up in an INFINITE loop of of a "DL".

The main reason was an DOUBLE DELETE of the SAME object from the list:

insert

before

MkDbgObjInstances: MkErrorC[0x563457fdeb00] prev<(nil)>, next<(nil)>, var<MkOBJ(new)>
1. new HEAD  0x563457fdeb00 BEFORE insert
MkDbgObjInstances: MkErrorC[0x563457fde5f0] prev<0x563457fddbd0>, next<0x563457fde0e0>, var<old>
2. old HEAD 0x563457fde5f0 
MkDbgTypInstances: MkErrorC[0x563457fac9c8] 0x563457fde5f0,0x563457fde0e0,0x563457fddbd0,
3. old HEAD 0x563457fde5f0 is FIRST in list

after

MkDbgObjInstances: MkErrorC[0x563457fdeb00] prev<0x563457fddbd0>, next<0x563457fde5f0>, var<MkOBJ(new)>
4. new HEAD  0x563457fdeb00 AFTER insert
MkDbgObjInstances: MkErrorC[0x563457fde5f0] prev<0x563457fdeb00>, next<0x563457fde0e0>, var<old>
5. old HEAD 0x563457fde5f0 is now SECOND
MkDbgTypInstances: MkErrorC[0x563457fac9c8] 0x563457fdeb00,0x563457fde5f0,0x563457fde0e0,0x563457fddbd0,
6. new HEAD  0x563457fdeb00 is FIRST in list

first delete

before

MkDbgErr[0x563457fdeb00]: check<1>, mkrt<ok>, isLocal<0>, format_of_error<0x563457fbd620>
00000000000000000 [rnel/c/MkErrorS_mk.c:154]
MkDbgTypInstances: MkErrorC[0x563457fac9c8] 0x563457fdeb00,0x563457fde5f0,0x563457fde0e0,0x563457fddbd0,
MkDbgObjInstances: MkErrorC[0x563457fdeb00] prev<0x563457fddbd0>, next<0x563457fde5f0>, var<MkOBJ(err)>
7. head 0x563457fdeb00 to be deleted

after

11111111111111111 [rnel/c/MkErrorS_mk.c:158]
MkDbgTypInstances: MkErrorC[0x563457fac9c8] 0x563457fde5f0,0x563457fde0e0,0x563457fddbd0,
MkDbgObjInstances: MkErrorC[0x563457fdeb00] prev<0x563457fddbd0>, next<0x563457fde5f0>, var<MkOBJ(err)>
8.  head 0x563457fdeb00 DONE but "prev" and "next" NOT cleared

second delete

before

22222222222222222 [rnel/c/MkErrorS_mk.c:162]
MkDbgTypInstances: MkErrorC[0x563457fac9c8] 0x563457fde5f0,0x563457fde0e0,0x563457fddbd0,
MkDbgObjInstances: MkErrorC[0x563457fdeb00] prev<0x563457fddbd0>, next<0x563457fde5f0>, var<MkOBJ(err)>
9. BROKEN: old head 0x563457fdeb00 to be deleted SECOND TIME

after

33333333333333333 [rnel/c/MkErrorS_mk.c:166]
MkDbgTypInstances: MkErrorC[0x563457fac9c8] 0x563457fde5f0,0x563457fde0e0,0x563457fddbd0,0x563457fde5f0,0x563457fde0e0,break
MkDbgObjInstances: MkErrorC[0x563457fdeb00] prev<0x563457fddbd0>, next<0x563457fde5f0>, var<MkOBJ(err)>
10. LIST is BROKEN → infinit loop because end with NULL never reached !!

[aotto1968]

patch for DL_DELETE2

#define DL_DELETE2(head,del,prev,next)                                                         \                              
do {                                                                                           \                              
  assert((head) != NULL);                                                                      \                              
  assert((del)->prev != NULL);                                                                 \                              
  if ((del)->prev == (del)) {                                                                  \                              
      (head)=NULL;                                                                             \                              
  } else if ((del) == (head)) {                                                                \                              
      assert((del)->next != NULL);                                                             \                              
      (del)->next->prev = (del)->prev;                                                         \                              
      (head) = (del)->next;                                                                    \                              
  } else {                                                                                     \                              
      (del)->prev->next = (del)->next;                                                         \                              
      if ((del)->next) {                                                                       \                              
          (del)->next->prev = (del)->prev;                                                     \                              
      } else {                                                                                 \                              
          (head)->prev = (del)->prev;                                                          \                              
      }                                                                                        \                              
  }                                                                                            \                              
  /* addon to get "assert" on double delete */ \                                                                              
  (del)->prev = NULL; \                                                                                                       
  (del)->next = NULL; \                                                                                                       
} while (0)  

patch for CDL_DELETE2

#define CDL_DELETE2(head,del,prev,next)                                                        \
do {                                                                                           \
  if (((head)==(del)) && ((head)->next == (head))) {                                           \
      (head) = NULL;                                                                           \
  } else {                                                                                     \
  /* addon to get "assert" on double delete */ \
     assert((del)->next != NULL); \
     assert((del)->prev != NULL); \
     (del)->next->prev = (del)->prev;                                                          \
     (del)->prev->next = (del)->next;                                                          \
     if ((del) == (head)) (head)=(del)->next;                                                  \
  }                                                                                            \
  /* addon to get "assert" on double delete */ \
  (del)->prev = NULL; \
  (del)->next = NULL; \
} while (0)

[Quuxplusone]

IIUC, you're asking to add this to the macro:

  /* addon to get "assert" on double delete */ \                                                                              
  (del)->prev = NULL; \                                                                                                       
  (del)->next = NULL; \ 

But that merely modifies the prev and next pointers of the element that you have just removed from the list! Since that element is no longer in the list, its prev and next pointers are irrelevant. Resetting them to NULL merely wastes CPU cycles.

Worse, there are actually use-cases where not resetting the prev and next pointers is part of the algorithm. For example: Knuth's Dancing Links.

If you're worried about catching bugs in your own code (as opposed to bugs in uthash), then you could always add that line to your own code:

DL_DELETE(head, mynode);
mynode->prev = mynode->next = NULL;

Alternatively, you could define your own "delete-and-reset-pointers" macro:

#define MY_DELETE(head, del) do { DL_DELETE(head, del); (del)->prev = (del)->next = NULL; } while (0)

[aotto1968]

ok, The assert from above only works if prev/next == NULL. double-delete without prev/next == NULL will create a very tricky bug and end in endless loop. I think it is part of the library to "self-protect" itself. If cpu-cycles are lost this is the price to pay.