2008-12-19 00:43 -!- pranith(ca4bcee2@webchat.mibbit.com) has joined #tux3 2008-12-19 02:58 folks 2008-12-19 02:58 bbl 2008-12-19 03:24 -!- bh(~billh@ip68-107-26-122.sd.sd.cox.net) has joined #tux3 2008-12-19 06:02 -!- bushman(~marcin@c-76-23-106-132.hsd1.sc.comcast.net) has joined #tux3 2008-12-19 08:42 -!- tim_dimm(~timothyhu@cpe-76-168-94-231.socal.res.rr.com) has joined #tux3 2008-12-19 10:15 -!- tim_dimm(~timothyhu@cpe-76-168-94-231.socal.res.rr.com) has joined #tux3 2008-12-19 11:45 -!- mingming(~mingming@32.97.110.51) has joined #tux3 2008-12-19 11:50 -!- tim_dimm(~timothyhu@cpe-76-168-94-231.socal.res.rr.com) has joined #tux3 2008-12-19 13:00 back into filemap.c 2008-12-19 13:01 hopefully, this is the last stretch of work to get something usable, until we get to versions 2008-12-19 13:03 so, the plan is, first we look in a dleaf and return a vector of segs - block/count - and holes for a given logical region 2008-12-19 13:04 (still waving my hands at extent overlap at the ends of the region) 2008-12-19 13:08 for write, extent allocations are then done and the segs list is updated, replacing the holes with new segments or redirecting existing segments to new locations (the segs list can become longer or shorter) 2008-12-19 13:09 then its time to insert the segs list back into the dleaf, this is the fun part 2008-12-19 13:10 from the initial scan, we should have a pointer to the first entry above the logical region 2008-12-19 13:11 we use the new dleaf_split_at to split out the tail of the leaf into a temporary leaf 2008-12-19 13:11 then use dwalk_pack to pack extents into the leaf, until the leaf fills 2008-12-19 13:12 then we create a new leaf by splitting the btree (don't have to split the leaf, we will be biased in favor of linear insertion and let the leaves be unbalanced for now) 2008-12-19 13:14 continue that until all the segs fit in the leaf (we break up long segs into our limited-size extents here, so we could generate more than one new leaf) 2008-12-19 13:15 when done, check if the leaf tail will fit, if not, split 2008-12-19 13:16 then merge the tail in using the existing dleaf_merge (also used for btree deletion, i.e., version delete or maybe later, hole punch) 2008-12-19 13:17 this is all pretty efficient... the larger logical regions we can work with, the more efficient 2008-12-19 13:17 now, I'm thinking split/merge is not good way 2008-12-19 13:18 now is the time to decide that 2008-12-19 13:18 split needs to copy 4 times 2008-12-19 13:18 good morning :) 2008-12-19 13:18 hi 2008-12-19 13:18 :) 2008-12-19 13:18 and merge also needs to copy 4 times 2008-12-19 13:19 I think we have to copy 8 times totally 2008-12-19 13:19 four times? 2008-12-19 13:19 (copy means memcpy()) 2008-12-19 13:20 in split, just two copies 2008-12-19 13:20 split is, extent, entry, group, and kill gap of entry and group 2008-12-19 13:21 usually, killing the gap is not needed 2008-12-19 13:21 if so, we need to change dwalk_pack? 2008-12-19 13:21 I think it assuming there is no gap 2008-12-19 13:22 there will be no gap when it is packing 2008-12-19 13:22 usually, number of groups will not change 2008-12-19 13:22 it will just be one group 2008-12-19 13:23 when it is more groups, it is a special case where the small extra overhead does not matter 2008-12-19 13:23 however, it can be 2008-12-19 13:23 yes 2008-12-19 13:23 but rare 2008-12-19 13:23 and we have to handle 2008-12-19 13:23 and it is a small overhead anyway 2008-12-19 13:23 yes 2008-12-19 13:23 the split handles it 2008-12-19 13:23 these functions are pretty efficient 2008-12-19 13:24 more efficient than looping over _pack to handle the tail 2008-12-19 13:24 yes 2008-12-19 13:24 but, we can create dwalk_insert 2008-12-19 13:24 yes, and we can view that as an opportunistic optimization 2008-12-19 13:25 when we hit a case that is not easily handled by dwalk_insert, we go to the split/merge 2008-12-19 13:25 the split/merge is inherently robust, because those operations _must_ be reliable, or the btree will be corrupt 2008-12-19 13:26 but, we make new dleaf_split_at? 2008-12-19 13:26 already done 2008-12-19 13:26 it was factored out of dleaf_split 2008-12-19 13:26 it was clean 2008-12-19 13:27 um... 2008-12-19 13:28 dwalk_insert will replace dwalk_pack, so I don't see extra complexicy 2008-12-19 13:28 how close are you with that? 2008-12-19 13:29 still need some work 2008-12-19 13:30 how does it handle the case where the leaf tail has to be moved? 2008-12-19 13:31 it means we have to split leaf in that case? 2008-12-19 13:31 or save tail issue? 2008-12-19 13:31 yes, that is the issue I am solving now 2008-12-19 13:32 For save tail issue, I'm going to use memmove() 2008-12-19 13:33 it's a little complex because the arrangement of groups can change 2008-12-19 13:33 yes 2008-12-19 13:34 so I am thinking, we handle the general case with split/merge, then optimize it with techniques like you are developing now 2008-12-19 13:34 however, it also use memmove() 2008-12-19 13:35 list, split moves things around, but it is efficient, and in many cases we will be able to avoid the split/merge completely 2008-12-19 13:35 expecially for linear writing to a new file 2008-12-19 13:36 if it is linear, insert will just add extent and entry 2008-12-19 13:36 yes 2008-12-19 13:36 ah 2008-12-19 13:36 yes 2008-12-19 13:37 in general, any case where dwalk_insert is easy to implement and reliable, we use it instead of split/merging the tail 2008-12-19 13:37 this gives us a robust strategy 2008-12-19 13:37 split/merge has another issue 2008-12-19 13:37 we may can merge after added new extents 2008-12-19 13:38 yes 2008-12-19 13:38 can't did you mean? 2008-12-19 13:38 how do we solve? 2008-12-19 13:38 I mentioned that above 2008-12-19 13:38 it is pretty easy 2008-12-19 13:38 ah, sorry, can't 2008-12-19 13:38 it is the same test as needed for btree coalesce 2008-12-19 13:39 make a conservative test that the tail will fit in the free space of the leaf, split if not 2008-12-19 13:39 split btree 2008-12-19 13:40 split two times? 2008-12-19 13:40 the split algorithm works pretty well, all the splitting ends up in the same place, splitting on dwalK_pack/dwalk_merge, and splitting on merging the tail 2008-12-19 13:40 there will be no extra splits 2008-12-19 13:41 ah 2008-12-19 13:41 no extra btree splits 2008-12-19 13:42 if we can't merge temporary buffer, we do real split 2008-12-19 13:42 yes 2008-12-19 13:42 that part works out pretty well 2008-12-19 13:43 I went through something like this with the inode table too, first I tried to have a classic btree split in the middle of the leaf 2008-12-19 13:43 that produced pretty bad behaviour 2008-12-19 13:43 and it was hard to think about the algorithm 2008-12-19 13:44 then it changed to creating a new, empty leaf in the btree when a table block fills up 2008-12-19 13:44 the create algorithm worked out better and the leaf block usage improved a lot 2008-12-19 13:45 there will be cases where we want a more balanced split, for example, random writes to a db file 2008-12-19 13:46 and then we will add a heuristic, for now we won't worry about it 2008-12-19 13:46 ok... I keep waving my hands at the extent overlap issue 2008-12-19 13:47 thinking that the main algorithm should work reliably first in the case that extents do not overlap, then add the cleanup for the ends of the logical region 2008-12-19 13:48 but really, it is better to have a plan for the handling of the ends now 2008-12-19 13:48 yes 2008-12-19 13:48 in the !create case, we just make the fixup in the segs vector 2008-12-19 13:48 that is easy, but not done for the top end yet 2008-12-19 13:50 the overlapping segments will be entered into the seg vector, so that the top segment is not part of the tail 2008-12-19 13:50 (I think) 2008-12-19 13:50 top extent I mean 2008-12-19 13:51 and the bottom overlapping extent will be in the segs list 2008-12-19 13:51 overlapping means 2~6, and 6~10 logcal region? 2008-12-19 13:52 that means 6 blocks and 10 blocks? 2008-12-19 13:52 start 2:size 4, start 6:size 5 2008-12-19 13:53 that does not overlap 2008-12-19 13:53 but your first example does 2008-12-19 13:54 existing extent: 2/6, create region 6/10 2008-12-19 13:54 overlap is not meaning, extents can be contiguous 2008-12-19 13:55 2/6 is index-2:count-6? 2008-12-19 13:55 in my example, extent 2/6 may have to end up as 2/4 if the physical extent is not contiguous, or may stay as 2/6, or get longer if a new physical extent above it is contiguous 2008-12-19 13:56 6 is count of blocks? 2008-12-19 13:56 yes 2008-12-19 13:56 so, I think we shouldn't make that case 2008-12-19 13:57 details? 2008-12-19 13:57 you think it will not happen, or we should not allow it? 2008-12-19 13:57 caller (e.g. filemap) should know about extent 2/6 2008-12-19 13:58 both is true 2008-12-19 13:58 well, we should not allow it 2008-12-19 13:58 yes, the caller that is doing the block allocations worries about this 2008-12-19 13:58 but get_segs has to tell it about the overlap 2008-12-19 13:59 because the segs[] vector does not represent that 2008-12-19 13:59 for this, I though we should use read_seg/write_seg 2008-12-19 13:59 I thought 2008-12-19 13:59 read_seg tells current extents 2008-12-19 14:00 user of read_seg, check it, then it decides what it want to do 2008-12-19 14:01 yes 2008-12-19 14:01 in the above case, user will try to create 7/9 (and if possible, contiguous with 2/6) 2008-12-19 14:01 yes 2008-12-19 14:02 and tell result of allocation to dleaf stuff 2008-12-19 14:02 I think 2008-12-19 14:02 right 2008-12-19 14:03 and I think dleaf should provide some function to do it 2008-12-19 14:03 I am thinking that caller gets a segs list from read_segs, does allocations and makes changes to the segs list, then calls write_segs to insert into the dtree 2008-12-19 14:03 add/insert/merge/update/truncate 2008-12-19 14:04 it can 2008-12-19 14:04 the walk_ api was supposed to be for that 2008-12-19 14:04 so the details remain exposed to the caller, which is going to do much more complex processing over time 2008-12-19 14:04 while still being a pretty simple api 2008-12-19 14:05 however, I guessed the packing those info and tell to another is not overkill 2008-12-19 14:05 add/insert/merge/update/truncate is operations that caller is needed 2008-12-19 14:05 I guess 2008-12-19 14:06 when we are deleting versioned segments, we can't really write that as a function in dleaf 2008-12-19 14:06 unless we want dleaf.c to know all about version details 2008-12-19 14:06 which is not a good factoring, I think 2008-12-19 14:06 i see 2008-12-19 14:07 that is one of the two reasons for the walk api 2008-12-19 14:07 dleaf can do it with versioning helper? 2008-12-19 14:07 the other reason is, it is efficient for multiple extents per operation 2008-12-19 14:07 that helper would be gigantic 2008-12-19 14:07 have a look at version.c 2008-12-19 14:08 but, in this case, dleaf stuff is including dwalk 2008-12-19 14:08 btw, in this case 2008-12-19 14:08 yes 2008-12-19 14:08 ok 2008-12-19 14:08 so what I wanted is to have the versioning code happening at as high a level as possible 2008-12-19 14:08 not in a helper 2008-12-19 14:09 it has to happen inside get_block of course 2008-12-19 14:09 ok 2008-12-19 14:09 but that is just for now until we have some kind of extent-oriented call from the vfs 2008-12-19 14:09 yes 2008-12-19 14:09 or we write our own handler for the mpage-type logic 2008-12-19 14:10 yes, I think we'll do it 2008-12-19 14:10 should give a measurable performance increase 2008-12-19 14:10 yes 2008-12-19 14:11 however, it is later 2008-12-19 14:11 yes 2008-12-19 14:11 did you fix the bug in the original version of dwalk_probe? 2008-12-19 14:11 no 2008-12-19 14:12 ok, well your new stuff, is it nearly solid except for dwalk_merge? 2008-12-19 14:12 dleaf_merge? 2008-12-19 14:12 I thought you were writing a dwalk_merge 2008-12-19 14:13 did I read that wrong? 2008-12-19 14:13 ah 2008-12-19 14:13 now, I'm writing dwalk_insert 2008-12-19 14:13 sorry 2008-12-19 14:13 I'll try dwalk_merge after it 2008-12-19 14:13 :) 2008-12-19 14:13 ok, well your new stuff, is it nearly solid except for dwalk_insert? 2008-12-19 14:13 and may dwalk_update 2008-12-19 14:14 I think so 2008-12-19 14:14 however, it will break dwalk_pack/dwalk_mock 2008-12-19 14:14 dwalk_pack works differently, or does not work at all? 2008-12-19 14:15 it doesn't work at all 2008-12-19 14:15 because the detail of struct dwalk was changed 2008-12-19 14:15 it would be nice if it worked :) 2008-12-19 14:15 yes 2008-12-19 14:15 dwalk_insert was replacement of it 2008-12-19 14:16 I would like to have both for now, and replace dwalk_pack over time 2008-12-19 14:16 and for now, I just need dwalk_pack to get filemap.c working reliably 2008-12-19 14:17 maybe, for it, I will need to adjust the detail of dwalk_pack 2008-12-19 14:18 if you could do that, and let me pull even with dwalk_insert not working, that would be nice 2008-12-19 14:19 dwalk_pack is assuming, leaf doesn't have entry/extent after target 2008-12-19 14:19 yes, that is perfect for me now 2008-12-19 14:19 ok 2008-12-19 14:20 I'll try 2008-12-19 14:20 ah 2008-12-19 14:21 btw, I'm thinking caller has another additional work 2008-12-19 14:21 caller should check maximum extent->count, and split it to two segements 2008-12-19 14:22 agreed, I wrote that up above 2008-12-19 14:22 in fact, it could be a lot of segments 2008-12-19 14:22 good 2008-12-19 14:23 ah, and pack takes one extent 2008-12-19 14:23 yes 2008-12-19 14:23 but, I think it should take multiple extents 2008-12-19 14:24 dwalk_pack should take multiple extents and try to merge them? 2008-12-19 14:24 no 2008-12-19 14:24 add multiple segemnts at once time 2008-12-19 14:25 to reduce overhead? 2008-12-19 14:25 yes 2008-12-19 14:25 well, maybe, it would be later 2008-12-19 14:26 yes 2008-12-19 14:27 because passed segments is contiguous, it shouldn't be complex to add multiple segments 2008-12-19 14:27 contiguous logical region 2008-12-19 14:32 btw, dwalk_mock seems strange 2008-12-19 14:34 where is initializing the walk->mock? 2008-12-19 14:38 the struct dwalk has the right state 2008-12-19 14:38 walk->mock.used and walk->mock.free 2008-12-19 14:38 it doesn't seem to be initialized 2008-12-19 14:43 initialized to zero 2008-12-19 14:43 and they accumulate the change 2008-12-19 14:43 free and used should have same value with current dleaf? 2008-12-19 14:44 no, they have the difference from the current dleaf values 2008-12-19 14:44 initial is also not same? 2008-12-19 14:45 if so, used - free is really strange 2008-12-19 14:45 right, they are initally zero, they could be initialized to the same as the dleaf, then they would be the same 2008-12-19 14:46 and dwalk_pack may not add entry 2008-12-19 14:46 and dwalk_pack may not add new entry 2008-12-19 14:46 right, it might just add a new extent 2008-12-19 14:46 I think it shouldn't happen for now 2008-12-19 14:46 because we don't allow multiple extents on one entry 2008-12-19 14:47 -!- andrem(~andre@201-1-148-5.dsl.telesp.net.br) has joined #tux3 2008-12-19 14:47 that is ok 2008-12-19 14:47 if it is allowed, we have to handle it by dwalk_probe() too 2008-12-19 14:47 and dwalk_index() 2008-12-19 14:48 those will always seek to an exact entry 2008-12-19 14:49 and we will handle the details of what is inside the entry in higher level code 2008-12-19 14:49 um... 2008-12-19 14:49 I can't see why doesn't it need to change entry_limit 2008-12-19 14:51 maybe it does 2008-12-19 14:52 um... 2008-12-19 14:52 it does change it, in the mock field 2008-12-19 14:53 oh 2008-12-19 14:53 inc_entry_limit(&walk->mock.entry, 1); 2008-12-19 14:54 it changes dleaf before split? 2008-12-19 14:54 what does? 2008-12-19 14:54 no 2008-12-19 14:54 inc_entry_limit() changes entry->limit? 2008-12-19 14:55 in the mock, no 2008-12-19 14:55 and mock is before btree_leaf_split 2008-12-19 14:55 yes 2008-12-19 14:55 it is just to find out of the new entries fit 2008-12-19 14:56 ah 2008-12-19 14:56 inc_entry_limit() in pack 2008-12-19 14:56 I'm missing it 2008-12-19 14:56 yes 2008-12-19 14:56 ok, in your new code 2008-12-19 14:57 I will be out for an hour 2008-12-19 14:58 ok, well, I'll try 2008-12-19 15:27 -!- tim_dimm(~timothyhu@cpe-76-168-94-231.socal.res.rr.com) has joined #tux3 2008-12-19 16:39 -!- tim_dimm(~timothyhu@cpe-76-168-94-231.socal.res.rr.com) has joined #tux3 2008-12-19 16:49 -!- tim_dimm(~timothyhu@cpe-76-168-94-231.socal.res.rr.com) has joined #tux3 2008-12-19 16:59 back 2008-12-19 17:00 I remembered dwalk_pack() is working 2008-12-19 17:00 nice 2008-12-19 17:00 maybe 2008-12-19 17:00 :) 2008-12-19 17:00 well, it will get some testing from me 2008-12-19 17:00 and I don't need _mock right now 2008-12-19 17:01 good 2008-12-19 17:01 pull? 2008-12-19 17:01 chop_after is needed? 2008-12-19 17:01 ACTION thinks 2008-12-19 17:01 it is also broken 2008-12-19 17:01 no 2008-12-19 17:01 that's ok 2008-12-19 17:01 it's being replaced with dleaf split/merge for the tail 2008-12-19 17:01 the whole thing is getting much nicer 2008-12-19 17:01 dwalk_pack is strange, however it will work 2008-12-19 17:02 strange? 2008-12-19 17:02 oh, funny to code 2008-12-19 17:02 e.g. walk->entry == walk->estop 2008-12-19 17:02 yes 2008-12-19 17:02 things being upside down helps make it strange 2008-12-19 17:02 and one byte pointers... 2008-12-19 17:03 I take full blame 2008-12-19 17:03 well, dwalk_pack doesn't update ->estop, but test it 2008-12-19 17:04 well, I'll review it 2008-12-19 17:04 the original did not test estop either 2008-12-19 17:05 did not update I mean 2008-12-19 17:05 bug? 2008-12-19 17:06 now, dwalk_pack also doesn't update ->estop 2008-12-19 17:06 can be bug 2008-12-19 17:06 however, it is assuming "add" operation 2008-12-19 17:06 so, maybe it works 2008-12-19 17:07 I don't see how ;) 2008-12-19 17:07 if we remove chop* and mock, it is very easy to work 2008-12-19 17:08 you can leave them in, just write a /* this is broken */ comment 2008-12-19 17:08 or assert(0) 2008-12-19 17:08 that will do 2008-12-19 17:08 dwalk_pack() also test dwalk_index(walk) != index, it will match always 2008-12-19 17:08 yes, so it is a bug that I covered up 2008-12-19 17:08 and you noticed, good 2008-12-19 17:09 easy to fix 2008-12-19 17:09 well, I'll review dwalk_pack fully 2008-12-19 17:09 why is it even testing estop? 2008-12-19 17:09 for other stuff, I can add "#if 0"? 2008-12-19 17:09 good 2008-12-19 17:10 ah, it meant - can I add "#if 0"? 2008-12-19 17:10 yes 2008-12-19 17:10 ok, good 2008-12-19 17:10 and I am thinking, that test of estop is bogus 2008-12-19 17:10 remove it to fix :) 2008-12-19 17:10 unit test will be also removed 2008-12-19 17:11 because it doesn't work? 2008-12-19 17:11 yes 2008-12-19 17:11 oh, one that depends on mock 2008-12-19 17:11 well, remove is "#if 0" actually 2008-12-19 17:11 sure 2008-12-19 17:11 I'll fix it to just do the _pack test 2008-12-19 17:11 mock? 2008-12-19 17:12 the unit test needs to be #ifdef 0 because _chop is broken? 2008-12-19 17:12 yes 2008-12-19 17:12 fine 2008-12-19 17:12 _chop and _chop_after and _mock 2008-12-19 17:13 well, it may be work 2008-12-19 17:13 but, I can't mark it as ok 2008-12-19 17:13 that is fine for now 2008-12-19 17:13 and I know the bug of _chop and _chop_after 2008-12-19 17:14 I don't want to fix those if we don't need 2008-12-19 17:14 right, not a good use of time 2008-12-19 17:14 static int get_segs(struct inode *inode, block_t start, unsigned limit, 2008-12-19 17:14 struct seg seg[], unsigned max_segs, unsigned *below, unsigned *above) <- revised get_segs interface 2008-12-19 17:14 this is the one you called read_segs 2008-12-19 17:15 so, I think we can merge now 2008-12-19 17:15 ok 2008-12-19 17:15 below, above? 2008-12-19 17:15 yes, the size of overlap below and above, needed only for create = 1 2008-12-19 17:16 ah, I assumed creater will adjust start and limit 2008-12-19 17:17 start - 1, and limit + 1 2008-12-19 17:17 caller can adjust them 2008-12-19 17:17 if it wants 2008-12-19 17:17 yes 2008-12-19 17:17 get_segs should say exactly what lies in the io region 2008-12-19 17:18 pull and review now? 2008-12-19 17:18 I'll check my patches 2008-12-19 17:18 I'll work on an email to describe the filemap.c strategy 2008-12-19 17:19 ok 2008-12-19 17:49 -!- tim_dimm(~timothyhu@cpe-76-168-94-231.socal.res.rr.com) has joined #tux3 2008-12-19 18:05 ugh, I've noticed dwalk_pack didn't work 2008-12-19 18:06 and I noticed why does current code work 2008-12-19 18:07 aha 2008-12-19 18:07 hard thing? 2008-12-19 18:08 dwalk_probe and others has different dwalk state entriely 2008-12-19 18:08 and dwalk_pack depends on it 2008-12-19 18:08 right, _probe is supposed to set up the right state for _pack 2008-12-19 18:09 as well as _next 2008-12-19 18:09 but, current _probe dones't do it 2008-12-19 18:09 whoops 2008-12-19 18:09 now, we use _back 2008-12-19 18:10 so, it works 2008-12-19 18:10 maybe, it is not hard to fix 2008-12-19 18:11 however, new filemap is how work? 2008-12-19 18:11 it still wants a _back 2008-12-19 18:11 bug it does not need _chop or _mock 2008-12-19 18:11 but 2008-12-19 18:11 I meant 2008-12-19 18:12 it's ok 2008-12-19 18:12 it needs _probe, _next, _back, _pack 2008-12-19 18:12 now, new _back has same state to _probe 2008-12-19 18:12 good 2008-12-19 18:12 _pack depends assumes old state 2008-12-19 18:12 bad ;) 2008-12-19 18:12 so, I have to fix _pack 2008-12-19 18:12 ok 2008-12-19 18:13 however, why new filemap doesn't need _chop_after? 2008-12-19 18:13 ah, it does 2008-12-19 18:14 i see 2008-12-19 18:14 do make the dleaf state consistent after the _packs are done 2008-12-19 18:14 so, I have to fix chop_after 2008-12-19 18:14 but 2008-12-19 18:14 it can be very simple 2008-12-19 18:15 well 2008-12-19 18:15 no 2008-12-19 18:15 however, maybe it is chop, not after? 2008-12-19 18:15 it is called before the packs 2008-12-19 18:15 yes, it's just chop 2008-12-19 18:15 chop, current extent and after? 2008-12-19 18:16 it chops current extent and after? 2008-12-19 18:16 yes 2008-12-19 18:16 ok 2008-12-19 18:16 I'll do it 2008-12-19 18:17 ok, I'll go back to work on filemap 2008-12-19 18:17 ok 2008-12-19 18:17 this is the most important part of tux3, the filemap and dwalk 2008-12-19 18:18 yes 2008-12-19 18:18 and it's getting close to usable, so I'm happy 2008-12-19 18:19