From: Konstantin Khlebnikov [mailto:koct9i@xxxxxxxxx] > On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox > <mawilcox@xxxxxxxxxxxxxxxxx> wrote: > > From: Matthew Wilcox <willy@xxxxxxxxxxxxx> > > > > The IDR is very similar to the radix tree. It has some functionality > > that the radix tree did not have (alloc next free, cyclic allocation, > > a callback-based for_each, destroy tree), which is readily implementable > > on top of the radix tree. A few small changes were needed in order to > > use a tag to represent nodes with free space below them. > > > > The IDA is reimplemented as a client of the newly enhanced radix tree. > > As in the current implementation, it uses a bitmap at the last level of > > the tree. > > I'm still see no reason for this. > > include/linux/idr.h | 128 ++-- > > include/linux/radix-tree.h | 5 +- > > init/main.c | 3 +- > > lib/idr.c | 1075 ------------------------------- > > lib/radix-tree.c | 536 +++++++++++++-- > > tools/testing/radix-tree/Makefile | 5 +- > > tools/testing/radix-tree/idr.c | 148 +++++ > > tools/testing/radix-tree/linux/idr.h | 1 + > > tools/testing/radix-tree/linux/kernel.h | 2 + > > tools/testing/radix-tree/main.c | 6 + > > tools/testing/radix-tree/test.h | 2 + > > 11 files changed, 701 insertions(+), 1210 deletions(-) A net deletion of 509 LOC isn't convincing (and 160 lines of the net addition are test suite, so 670LOC in the kernel proper)? How about this from 0day? | -1328 | TOTAL | 9fdfa3f7ac88 Reimplement IDR and IDA using the radix tree | That's a saving of 1.3kB (mostly of kernel text) from deleting the IDR code. Then we can look at runtime memory savings. Having one pool of radix_tree_nodes that both the IDR and the radix tree usages pull from is a better use of memory than having one pool of radix_tree_nodes and another pool of idr_layers. I haven't measured the memory savings here, but on my workstation, I have 531 active_objs of IDR layers with 531 allocated objects (177 pages) and 13808 active / 13902 allocated radix_tree_nodes (1986 pages). If we combine the two, I estimate we'd save about 114 pages (456kB), which isn't a huge amount, but it's not nothing. There's also a question of testing; having two APIs is still bad, and I think the two APIs should be combined somehow, but having the same underlying data structure is an improvement towards code coverage. Note there's *no* IDR test suite today. ��.n��������+%������w��{.n�����{���)�� jg��� �����ݢj����G���� ���j:+v���w�m������w�������h�����٥
