| Keybuk | sadmac: I'll digest it over the next day or so, but that looks ... inspired | 00:40 |
|---|---|---|
| Keybuk | sadmac: around? | 14:35 |
| sadmac | Keybuk: ya? | 14:54 |
| Keybuk | sadmac: so what I think you're doing here, after a quick glance, is placing a second "iterator head" in the linked list immediately after the node being iterated | 14:56 |
| sadmac | immediately before | 14:56 |
| Keybuk | before? | 14:56 |
| sadmac | yes | 14:56 |
| Keybuk | ah, that explains why it's more complicated than I expected | 14:56 |
| sadmac | we're always operating on the node after the "cursor" element | 14:56 |
| sadmac | hmm, after would make a few things easier.... | 14:57 |
| sadmac | I need to get on campus, but I should be online in a couple minutes. | 15:03 |
| sadmac | brb. | 15:03 |
| Keybuk | yeah, just thinking about the difference | 15:04 |
| Keybuk | I'd thought about putting the cursor after, since then the node to return is cursor->prev and the next node to visit is cursor->next | 15:04 |
| Keybuk | and the worst they can do is remove all of the nodes | 15:04 |
| Keybuk | in which case, cursor->next is the list head, which will end the loop | 15:04 |
| Keybuk | if they remove the next node, that just means cursor->next is different | 15:05 |
| Keybuk | if they remove the visiting node, that just means cursor->prev is different - but we don't even look at that on the loop iteration | 15:05 |
| Keybuk | the bug is caused by "caching" the next node, so the visiting node can be removed | 15:06 |
| Keybuk | which means if you remove the next node as well, the cache dereferences free'd memory | 15:07 |
| Keybuk | by using a cursor element, we only ever cache the cursor, which in theory the code in the loop knows nothing about | 15:07 |
| Keybuk | -- | 15:07 |
| Keybuk | cursor after does mean that if new nodes are inserted after the visiting node, they will not be visited | 15:07 |
| Keybuk | not sure if that's a feature or not | 15:07 |
| Keybuk | cursor before means that new nodes inserted after *are* visited | 15:07 |
| Keybuk | but also, strangely, new nodes inserted before might be visited too | 15:08 |
| Keybuk | except you have a more complicated "step the cursor" case | 15:08 |
| Keybuk | and I'm not sure that "step the cursor" is robust if nodes are inserted before the visited node | 15:08 |
| Keybuk | in fact, I have a slight feeling that you'll visit the node twice | 15:08 |
| Keybuk | C-V-X on beginning of loop, becomes | 15:08 |
| Keybuk | C-A-B-V-X on end of loop | 15:09 |
| Keybuk | you'll see that C-next is not V, so won't step the cursor | 15:09 |
| Keybuk | so will visit A, B then V again | 15:09 |
| Keybuk | cursor after is safe from that | 15:09 |
| Keybuk | V-C-X becomes V-A-B-C-X or A-B-V-C-X | 15:09 |
| Keybuk | in neither case will A or B be visited in that iteration | 15:09 |
| sadmac | hm | 15:27 |
| sadmac | we could mark the cursor as special, either with a flag or by checking the address, and then modify the insert functions to behave as we'd expect. | 15:31 |
| sadmac | so V-C-X becomes A-B-V-C-X or V-C-A-B-X | 15:32 |
| Keybuk | I can't decide whether it's a good thing or not ;P | 15:32 |
| Keybuk | if it works with insert() you'd kinda expect it to work with insert_before() too | 15:32 |
| sadmac | the assumption from the "user" is that the list is being iterated linearly. | 15:33 |
| sadmac | before the visited node is not in the damage path | 15:33 |
| sadmac | after is | 15:33 |
| Keybuk | there's an even more fun way of doing it | 15:33 |
| Keybuk | actually, no, that's the same way you're trying to do it, sorry | 15:34 |
| sadmac | heh | 15:34 |
| Keybuk | I was thinking of actually removing the visited node, and use the cursor as a list head only | 15:34 |
| Keybuk | but that has exactly the same semantics anyway | 15:34 |
| sadmac | having nodes inserted after the visited node get iterated and before not is how it would work in the "oracle" case, where we just could divine where we were in the list by magic. | 15:36 |
| Keybuk | err, that wasn't english? | 15:36 |
| sadmac | putting it another way: | 15:37 |
| sadmac | X-A-X-X-X-V-X-X-B | 15:37 |
| sadmac | ^if we're at V, and we just inserted A and B, we'd expect A not to get visited and B to get visited | 15:38 |
| sadmac | that's what regular old NIH_FOREACH would do | 15:38 |
| Keybuk | right | 15:38 |
| sadmac | so we should emulate that behavior | 15:38 |
| sadmac | we want to visit things inserted after, but not things inserted before | 15:39 |
| Keybuk | agree | 15:39 |
| sadmac | so the way to do that is if a node is before a cursor and we try to insert_after, to insert after the cursor instead of right after the node | 15:40 |
| suihkulokki | is there some plan to add dh_installevent style helper | 15:41 |
| sadmac | suihkulokki: I have no idea what that is | 15:41 |
| suihkulokki | that's a debianism | 15:42 |
| sadmac | that'd do it | 15:42 |
| Keybuk | suihkulokki: no, none | 15:42 |
| suihkulokki | Keybuk: do you think it would be a good idea? | 15:42 |
| suihkulokki | this is the third package i'm adding a native upstart event file and I'm noticing a pattern ;) | 15:43 |
| sadmac | suihkulokki: who knows what the pattern will look like next release though ;) | 15:44 |
| Keybuk | suihkulokki: I do not think dh_ anything is a good idea | 15:46 |
| Keybuk | what's wrong with just shipping the file as a conffile? | 15:46 |
| suihkulokki | the point is just to cut down the lines written to each debian/rules file | 15:49 |
| Keybuk | sadmac: of course, I forgot that nih_list is kinda backwards | 15:49 |
| Keybuk | nih_list_add actually adds before :p | 15:49 |
| Keybuk | it's only nih_list_add_after that's special | 15:49 |
| sadmac | Keybuk: right | 15:49 |
| Keybuk | suihkulokki: why do you need any lines in debian/rules? | 15:50 |
| Keybuk | sadmac: so you have to try very hard to get the node *after* the one you're looking at | 15:50 |
| Keybuk | and because you tried hard, you're likely to expect that it gets iterated | 15:50 |
| sadmac | Keybuk: so in order to dtrt we need to be able to tell cursors from normal elements | 15:51 |
| sadmac | Keybuk: and we can do that one of 2 ways | 15:51 |
| sadmac | Keybuk: 1) the obvious way: add a field to the element with a flag | 15:51 |
| Keybuk | expensive | 15:51 |
| Keybuk | 64 bits! for a 1 bit flag | 15:52 |
| sadmac | Keybuk: 2) The evil way: check the address. If its allocated on the stack, its a cursor. if its in heap, its not | 15:52 |
| Keybuk | list elements can be alocated on the stack | 15:52 |
| sadmac | you're only technically right, I don't think they ever /are/ | 15:52 |
| Keybuk | yeah they are | 15:52 |
| sadmac | but, hence the evil | 15:52 |
| sadmac | hm | 15:53 |
| sadmac | we need darker magic | 15:53 |
| Keybuk | parse_job.c has one | 15:53 |
| Keybuk | parse_job.c: NihList stack; | 15:53 |
| sadmac | that'll do it | 15:54 |
| sadmac | we could add the flag field, and just come up with lots of ultra cool features so we need more flags :) | 15:54 |
| sadmac | nih_list_set_flag(list, NIH_EAT_BABIES_AND_KITTENS); | 15:55 |
| Keybuk | mmm, kittehs | 15:55 |
| Keybuk | your dual for loop really confuses me :p | 15:59 |
| Keybuk | this is you trying to do "before and after" code, right? :) | 16:00 |
| sadmac | yeah | 16:02 |
| Keybuk | couldn't the "test" part of the outer for loop just be 0 ? | 16:02 |
| Keybuk | for (NihList cursor = { &cursor, &cursor }, *_iter = nih_list_add_after ((list), &cursor); FALSE; nih_list_remove (&cursor)) | 16:03 |
| Keybuk | something like that | 16:03 |
| Keybuk | ie. don't set the pointer to NULL, then you don't need to test it | 16:03 |
| Keybuk | I suspect the compiler will optimise that properly anyway, but it makes it a bit more clear | 16:04 |
| Keybuk | I don't think you even need _iter in there | 16:04 |
| Keybuk | except as something to allow you call nih_list_add_after | 16:04 |
| sadmac | no that won't work | 16:05 |
| sadmac | then the loop will never run | 16:05 |
| sadmac | setting to null makes it run exactly once | 16:05 |
| sadmac | because its not null for the first test | 16:06 |
| Keybuk | ah, you're quite right | 16:07 |
| sadmac | Keybuk: I'm going to leave it up to you to figure out how to remove the handler function patch from bzr. Its tangled up in quite a few things. | 16:16 |
| Keybuk | handler function patch? | 16:18 |
| sadmac | Keybuk: our previous patchwork fix for a single instance of this error | 16:21 |
| sadmac | with the marking and sweeping and such | 16:22 |
| Keybuk | that's easy | 16:22 |
| Keybuk | bzr diff -r -2..-1 | 16:22 |
| Keybuk | or just bzr diff -r -1..-2 then you don't need -R to patch ;) | 16:22 |
| sadmac | Keybuk: its tangled with some other changes | 16:23 |
| Keybuk | ah, so it is | 16:23 |
| sadmac | Keybuk: its got the change of the dbus timeout to INT_MAX in there, and it also seems you moved some files | 16:23 |
| Keybuk | something like bzr diff -r before:594.1.2 I think | 16:24 |
| sadmac | tried that but the patch looked weird | 16:25 |
| sadmac | I think you renamed nih_dbus_tool.py to nih_dbus_tool in the same timeframe | 16:25 |
| Keybuk | no, the latter is just made from the former | 16:25 |
| sadmac | the diff I got back was re-adding the INT_MAX change | 16:25 |
| sadmac | like it wasn't there before | 16:26 |
| Keybuk | that merged from you at the same time I think | 16:26 |
| sadmac | hm | 16:30 |
| Keybuk | + if (_##iter->next == iter) { \ | 16:31 |
| Keybuk | + } \ | 16:31 |
| Keybuk | + iter = _##iter->next; \ | 16:31 |
| Keybuk | *cough* | 16:31 |
| Keybuk | shouldn't that last "=" be inside the if? :p | 16:31 |
| Keybuk | no | 16:32 |
| Keybuk | sorry | 16:32 |
| Keybuk | confusing iter and _##iter | 16:32 |
| Keybuk | you don't need the "tmp" inside though ;) | 16:35 |
| Keybuk | you know that _##iter->next and iter are the same | 16:35 |
| Keybuk | + if (_##iter->next == iter) { \ | 16:35 |
| Keybuk | + nih_list_add_after (iter, \ | 16:35 |
| Keybuk | + nih_list_remove (_##iter)); \ | 16:35 |
| Keybuk | + } \ | 16:35 |
| Keybuk | + iter = _##iter->next; | 16:35 |
| Keybuk | in fact | 16:37 |
| Keybuk | you don't even need it that complicatedf | 16:37 |
| Keybuk | if (_##iter->next == iter) | 16:37 |
| Keybuk | nih_list_add_after (iter, _##iter); | 16:37 |
| Keybuk | iter = _##iter->next; | 16:37 |
| Keybuk | yeah | 16:42 |
| Keybuk | confirmed | 16:42 |
| Keybuk | your method is unsafe when using nih_list_add () | 16:42 |
| Keybuk | if the caller does nih_list_add () on the entry itself, the cursor will be pushed back in the list | 16:43 |
| Keybuk | it correctly won't step | 16:43 |
| Keybuk | but will visit the entry twice | 16:43 |
| Keybuk | not that I can think of any time off-hand where we do that (I tend to call it on the list head), but it's valid - as it's a way of doing sorting and stuff | 16:43 |
| sadmac | ok | 16:57 |
| sadmac | so we need to have the cursor after | 16:57 |
| sadmac | and then add_after needs to have something done to it | 16:57 |
| Keybuk | cursor afterwards just has opposite problems | 17:01 |
| sadmac | how so? | 17:01 |
| Keybuk | it doesn't notice the adds at all :) | 17:01 |
| Keybuk | I'm actually wondering if there's an evil way of breaking the pointers :p | 17:02 |
| sadmac | which is half-right | 17:02 |
| sadmac | not noticing the adds is right for add(before) but not for add_after | 17:02 |
| sadmac | the latter is fixable | 17:02 |
| sadmac | hmm..actually you're right. we just need to fix one of the add methods to account for cursors | 17:03 |
| sadmac | the issue is the cursor getting separated from the iterated node in cases where the iterated node is still in the list | 17:04 |
| Keybuk | right, we really want to add them after the cursor | 17:11 |
| sadmac | assuming we switch to cursor after | 17:14 |
| sadmac | we need to add before the cursor if we keep it as is | 17:15 |
| Keybuk | right, which means you need to know where they started adding | 17:15 |
| Keybuk | am thinking | 17:16 |
| Keybuk | what if iter->next is cursor->next | 17:16 |
| Keybuk | so the list is slightly broken | 17:16 |
| Keybuk | (iter->next would normally be cursor) | 17:16 |
| sadmac | I'm afraid | 17:16 |
| Keybuk | no, there's no safe way to do that | 17:24 |
| Keybuk | the only way is to hide the cursor entirely | 17:25 |
| Keybuk | but then the cursor isn't actually updated | 17:25 |
| sadmac2 | there's one 8-byte solution | 17:36 |
| sadmac2 | we just need to make it smaller | 17:36 |
| sadmac2 | only thing I have so far is put a flag in the MSB of one of the poiters | 17:39 |
| sadmac2 | *pointers | 17:39 |
| Keybuk | pointers don't have MSBs | 17:40 |
| sadmac2 | they can be made to look as though they do. | 17:40 |
| Keybuk | no, they can't | 17:43 |
| Keybuk | you can't fiddle with a pointer, it's in scary undefined territory according to the spec | 17:43 |
| sadmac2 | yeah yeah | 17:44 |
| sadmac2 | this is what I get for reading kernel code | 17:44 |
| sadmac2 | now to class | 17:46 |
| === Md_ is now known as Md | ||
| Keybuk | #define NIH_LIST_FOREACH_SAFE(list, iter) \ | 19:14 |
| Keybuk | for (NihList _##iter = { &_##iter, &_##iter }, \ | 19:14 |
| Keybuk | *iter = nih_list_add_after ((list)->next, &_##iter)->prev; \ | 19:14 |
| Keybuk | iter != (list) && iter != &_##iter; \ | 19:14 |
| Keybuk | iter = nih_list_add_after (_##iter.next, &_##iter)->prev) | 19:14 |
| Keybuk | no, that doesn't quite work, since it leaves the cursor in the list | 19:19 |
| sadmac2 | Keybuk: that's what the outer for was for | 19:40 |
| Keybuk | #define NIH_LIST_FOREACH_SAFE(list, iter) \ | 20:45 |
| Keybuk | for (NihList _##iter##_cursor = { &_##iter, &_##iter }, \ | 20:45 |
| Keybuk | _##iter = &_##iter##_cursor; \ | 20:45 |
| Keybuk | _##iter; \ | 20:45 |
| Keybuk | nih_list_destroy (_##iter), _##iter = NULL) \ | 20:45 |
| Keybuk | for (NihList *iter = nih_list_add_after ((list)->next, _##iter)->prev; \ | 20:45 |
| Keybuk | iter != (list) && iter != _##iter; \ | 20:45 |
| Keybuk | iter = nih_list_add_after (_##iter->next, _##iter)->prev) | 20:45 |
| Keybuk | # | 20:45 |
| sadmac2 | Keybuk: is it ok to call nih_list_destroy on something stack-allocated? | 20:47 |
| sadmac2 | Keybuk: and either way, why isn't it nih_list_remove? | 20:47 |
| Keybuk | yeah, it just cuts it out of he list | 20:47 |
| Keybuk | destroy is cheaper than remove :p | 20:47 |
| sadmac2 | ah | 20:47 |
| Keybuk | destroy => nih_list_cut () | 20:47 |
| Keybuk | remove => nih_list_cut (), nih_list_init () | 20:47 |
| sadmac2 | yeah | 20:48 |
| sadmac2 | Keybuk: don't you need a * on line 2 before _##iter ? | 20:51 |
| Keybuk | yes | 20:53 |
| sadmac2 | Keybuk: it looks good. It has the issue of missing insertions that we expected | 21:00 |
| sadmac2 | Keybuk: so its just down to that | 21:00 |
| sadmac2 | adding the flag costs us 64 bits (128 if you allocated it with a free-list-based malloc) | 21:03 |
| sadmac2 | Keybuk: could we use a char for the flag, and then add the gcc flag for struct packing to get rid of the overallocation? | 21:04 |
| sadmac2 | damn, but putting it in an unpacked struct would still round it up again | 21:04 |
| Keybuk | indeed, very expensive for a single bit flag | 21:14 |
| sadmac2 | Keybuk: we could keep a global list of cursors | 21:19 |
| Keybuk | that's 64-128 bits each | 21:20 |
| sadmac2 | Keybuk: but only for the cursors | 21:20 |
| sadmac2 | Keybuk: not for /every/ list node | 21:21 |
| Keybuk | true | 21:21 |
| Keybuk | you need to check for cursorness on every insertion though | 21:21 |
| sadmac2 | Keybuk: only on insert_after | 21:23 |
| sadmac2 | Keybuk: which as you said is the far rarer case | 21:24 |
| Keybuk | no, both | 21:24 |
| Keybuk | nih_list_add (iter->next, entry) | 21:24 |
| Keybuk | you need to check whether iter->next is a cursor | 21:24 |
| sadmac2 | yeah | 21:25 |
| sadmac2 | the check is one comparison | 21:25 |
| sadmac2 | not a terrible expense | 21:25 |
| sadmac2 | we get a jump when it /is/ a cursor | 21:25 |
| sadmac2 | but other than that its 2 instructions | 21:25 |
| sadmac2 | oh, wait | 21:25 |
| sadmac2 | we're still on the list of cursors idea | 21:26 |
| * sadmac2 is on to his next, more evil thought | 21:26 | |
| sadmac2 | what if we added the flag field, but only when it was a cursor | 21:26 |
| sadmac2 | ? | 21:26 |
| sadmac2 | so when we call nih_list_new, which means we are getting a struct which is not attached to an object, we over-allocate by 64 bits | 21:28 |
| sadmac2 | and write 0xdeadbeafcafebabe /after/ the struct | 21:28 |
| Keybuk | unreliable | 21:29 |
| sadmac2 | where's the hole? | 21:29 |
| Keybuk | you don't know that all structs in the list are that long | 21:29 |
| Keybuk | and you don't know the user isn't using that exact string :p | 21:29 |
| Keybuk | e.g. the list head is smaller, you'd read unallocated memory | 21:29 |
| sadmac2 | user using the exact string is one in several billion billion | 21:29 |
| sadmac2 | struct not that long isn't possible due to struct member allignment | 21:29 |
| sadmac2 | (well, 32-bit folk get jacked a bit) | 21:30 |
| sadmac2 | we have a different value for cursors, and regular stack-allocated lists have stack space in front of them supplying the bullshit | 21:31 |
| Keybuk | no, it's entirely possible | 21:31 |
| Keybuk | I don't like even remote chances | 21:32 |
| Keybuk | it must only succeed _if_ it's a cursor | 21:32 |
| Keybuk | not just something that looks like one | 21:32 |
| sadmac2 | better odds? make the value a hash of the prev and next pointers | 21:32 |
| Keybuk | no | 21:33 |
| sadmac2 | you wouldn't do well in cryptography :) | 21:35 |
| Keybuk | it must only succeed if it is a cursor, not if it looks like one | 21:35 |
| Keybuk | and, pointedly, it mustn't crash on the list head <g> | 21:35 |
| sadmac2 | we could set aside some memory at startup, and allocate all cursors in it | 21:36 |
| sadmac2 | then we could check address range | 21:36 |
| Keybuk | what if you run out of that memory? | 21:44 |
| sadmac2 | get a bigger chunk and rename | 21:44 |
| sadmac2 | Keybuk: the check if on stack method works if we just enforce via documentation | 21:50 |
| sadmac2 | Keybuk: are you sure the example you found was on the stack, not a global? | 21:50 |
| Keybuk | definitely on the stack | 22:42 |
Generated by irclog2html.py 2.7 by Marius Gedminas - find it at mg.pov.lt!