Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1543737 > unrolled thread

Re: [RFC 00/10] implement alternative and much simpler id allocator

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC 00/10] implement alternative and much simpler id allocator Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2016-12-16 21:40 +0100
    RE: [RFC 00/10] implement alternative and much simpler id allocator Matthew Wilcox <mawilcox@microsoft.com> - 2016-12-16 22:30 +0100
    RE: [RFC 00/10] implement alternative and much simpler id allocator Matthew Wilcox <mawilcox@microsoft.com> - 2016-12-17 14:30 +0100
      Re: [RFC 00/10] implement alternative and much simpler id allocator Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2016-12-23 00:50 +0100
        RE: [RFC 00/10] implement alternative and much simpler id allocator Matthew Wilcox <mawilcox@microsoft.com> - 2016-12-23 18:20 +0100
    RE: [RFC 00/10] implement alternative and much simpler id allocator Matthew Wilcox <mawilcox@microsoft.com> - 2016-12-18 03:50 +0100

#1543737 — Re: [RFC 00/10] implement alternative and much simpler id allocator

On Fri, Dec 16 2016, Matthew Wilcox <mawilcox@microsoft.com> wrote:

> From: Andrew Morton [mailto:akpm@linux-foundation.org]
>> On Thu,  8 Dec 2016 02:22:55 +0100 Rasmus Villemoes
>> <linux@rasmusvillemoes.dk> wrote:
>> > TL;DR: these patches save 250 KB of memory, with more low-hanging
>> > fruit ready to pick.
>> >
>> > While browsing through the lib/idr.c code, I noticed that the code at
>> > the end of ida_get_new_above() probably doesn't work as intended: Most
>> > users of ida use it via ida_simple_get(), and that starts by
>> > unconditionally calling ida_pre_get(), ensuring that ida->idr has
>> > 8==MAX_IDR_FREE idr_layers in its free list id_free. In the common
>> > case, none (or at most one) of these get used during
>> > ida_get_new_above(), and we only free one, leaving at least 6 (usually
>> > 7) idr_layers in the free list.
>> 
>> I expect we'll be merging patches 1-32 of that series into 4.10-rc1 and
>> the above patch (#33) into 4.11-rc1.
>
> Hi Rasmus,
>
> Thanks for your work on this; you've really put some effort into
> proving your work has value.  My motivation was purely aesthetic, but
> you've got some genuine savings here (admittedly it's about a quarter
> of a cent's worth of memory with DRAM selling for $10/GB).
> Nevertheless, that adds up over a billion devices, and there are still
> people trying to fit Linux into 4MB embedded devices.
>

Yeah, my main motivation was embedded devices which don't have the
luxury of measuring their RAM in GB. E.g., it's crazy that the
watchdog_ida effectively use more memory than the .text of the watchdog
subsystem, and similarly for the kthread workers, etc., etc.. I didn't
mean for my patches to go in as is, more to provoke some discussion. I
wasn't aware of your reimplementation, but it seems that may make the
problem go away.

> I think my reimplementation of the IDA on top of the radix tree is
> close enough to your tIDA in memory consumption that it doesn't
> warrant a new data structure.
>
> On a 64-bit machine, your tIDA root is 24 bytes; my new IDA root is 16
> bytes.  If you allocate only one entry, you'll allocate 8 bytes.
> Thanks to the slab allocator, that gets rounded up to 32 bytes.  I
> allocate the full 128 byte leaf, but I store the pointer to it in the
> root (unlike the IDR, the radix tree doesn't need to allocate a layer
> for a single entry).  So tIDA wins on memory consumption between 1 and
> 511 IDs, and newIDA is slightly ahead between 512 and 1023 IDs.

This sounds good. I think there may still be a lot of users that never
allocate more than a handful of IDAs, making a 128 byte allocation still
somewhat excessive. One thing I considered was (exactly as it's done for
file descriptor tables) to embed a single word in the struct ida and
use that initially; I haven't looked closely at newIDA, so I don't know
how easy that would be or if its worth the complexity.

Rasmus

[toc] | [next] | [standalone]

#1543759

From: Rasmus Villemoes [mailto:linux@rasmusvillemoes.dk]
> On Fri, Dec 16 2016, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> > Thanks for your work on this; you've really put some effort into
> > proving your work has value.  My motivation was purely aesthetic, but
> > you've got some genuine savings here (admittedly it's about a quarter
> > of a cent's worth of memory with DRAM selling for $10/GB).
> > Nevertheless, that adds up over a billion devices, and there are still
> > people trying to fit Linux into 4MB embedded devices.
> >
> 
> Yeah, my main motivation was embedded devices which don't have the
> luxury of measuring their RAM in GB. E.g., it's crazy that the
> watchdog_ida effectively use more memory than the .text of the watchdog
> subsystem, and similarly for the kthread workers, etc., etc.. I didn't
> mean for my patches to go in as is, more to provoke some discussion. I
> wasn't aware of your reimplementation, but it seems that may make the
> problem go away.

It certainly shrinks the problem down to a size where it may not be worth introducing another implementation.

> > On a 64-bit machine, your tIDA root is 24 bytes; my new IDA root is 16
> > bytes.  If you allocate only one entry, you'll allocate 8 bytes.
> > Thanks to the slab allocator, that gets rounded up to 32 bytes.  I
> > allocate the full 128 byte leaf, but I store the pointer to it in the
> > root (unlike the IDR, the radix tree doesn't need to allocate a layer
> > for a single entry).  So tIDA wins on memory consumption between 1 and
> > 511 IDs, and newIDA is slightly ahead between 512 and 1023 IDs.
> 
> This sounds good. I think there may still be a lot of users that never
> allocate more than a handful of IDAs, making a 128 byte allocation still
> somewhat excessive. One thing I considered was (exactly as it's done for
> file descriptor tables) to embed a single word in the struct ida and
> use that initially; I haven't looked closely at newIDA, so I don't know
> how easy that would be or if its worth the complexity.

Heh, I was thinking about that too.  The radix tree supports "exceptional entries" which have the bottom bit set.  On a 64-bit machine, we could use 62 of the bits in the radix tree root to store the ID bitmap.  I'm a little wary of the potential complexity, but we should try it out.

Did you come up with any fun tests that could be added to the test-suite?  It feels a little slender right now.

[toc] | [prev] | [next] | [standalone]

#1543970

From: Matthew Wilcox
> From: Rasmus Villemoes [mailto:linux@rasmusvillemoes.dk]
> > This sounds good. I think there may still be a lot of users that never
> > allocate more than a handful of IDAs, making a 128 byte allocation still
> > somewhat excessive. One thing I considered was (exactly as it's done for
> > file descriptor tables) to embed a single word in the struct ida and
> > use that initially; I haven't looked closely at newIDA, so I don't know
> > how easy that would be or if its worth the complexity.
> 
> Heh, I was thinking about that too.  The radix tree supports "exceptional
> entries" which have the bottom bit set.  On a 64-bit machine, we could use 62
> of the bits in the radix tree root to store the ID bitmap.  I'm a little wary of the
> potential complexity, but we should try it out.

Test patch here: http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-12-16
It passes the test suite ... which I actually had to adjust because it now succeeds in cases where it hadn't (allocating ID 0 without preallocating), and it will now fail in cases where it hadn't previously (assuming a single preallocation would be enough).  There shouldn't be any examples of that in the kernel proper; it was simply me being lazy when I wrote the test suite.

[toc] | [prev] | [next] | [standalone]

#1546647

On Sat, Dec 17 2016, Matthew Wilcox <mawilcox@microsoft.com> wrote:

> From: Matthew Wilcox
>> From: Rasmus Villemoes [mailto:linux@rasmusvillemoes.dk]
>> > This sounds good. I think there may still be a lot of users that never
>> > allocate more than a handful of IDAs, making a 128 byte allocation still
>> > somewhat excessive. One thing I considered was (exactly as it's done for
>> > file descriptor tables) to embed a single word in the struct ida and
>> > use that initially; I haven't looked closely at newIDA, so I don't know
>> > how easy that would be or if its worth the complexity.
>> 
>> Heh, I was thinking about that too.  The radix tree supports "exceptional
>> entries" which have the bottom bit set.  On a 64-bit machine, we could use 62
>> of the bits in the radix tree root to store the ID bitmap.  I'm a little wary of the
>> potential complexity, but we should try it out.
>
> Test patch here: http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-12-16
> It passes the test suite ... which I actually had to adjust because it
> now succeeds in cases where it hadn't (allocating ID 0 without
> preallocating), and it will now fail in cases where it hadn't
> previously (assuming a single preallocation would be enough).  There
> shouldn't be any examples of that in the kernel proper; it was simply
> me being lazy when I wrote the test suite.

Nice work! A few random comments/questions:

- It does add some complexity, but I think a few comments would make it
  more digestable.

- Hm, maybe I'm confused, and I certainly don't understand how the whole
  radix tree works. But do you use every leaf node as an exceptional
  entry initially, to allocate the first 62 ids from that level? This
  code

	if ((bit + RADIX_TREE_EXCEPTIONAL_SHIFT) <
					BITS_PER_LONG) {
		bit += RADIX_TREE_EXCEPTIONAL_SHIFT;
		radix_tree_iter_replace(root, &iter, slot,
				(void *)((1UL << bit) |
				RADIX_TREE_EXCEPTIONAL_ENTRY));
		*id = new;
		return 0;
	}

   operates on bit, which is the offset from index*IDA_BITMAP_BITS, and
   it seems to create an exceptional entry somewhere down the tree
   (which may of course be the root).

   But we don't seem to allocate another bit from that exceptional entry
   ever unless it happened to sit at index 0; the code

	unsigned long tmp = (unsigned long)bitmap;
	if (start < BITS_PER_LONG) {
		unsigned tbit = find_next_zero_bit(&tmp,
					BITS_PER_LONG, start);
		if (tbit < BITS_PER_LONG) {
			tmp |= 1UL << tbit;
			rcu_assign_pointer(*slot, (void *)tmp);
			*id = new + tbit -
				RADIX_TREE_EXCEPTIONAL_SHIFT;
			return 0;
		}
	}

   is only used for small values of start (though it does seem to
   account for a non-zero value of new == iter.index * IDA_BITMAP_BITS).
   
- In the micro-optimization department, I think we should avoid
  find_next_zero_bit on a single word, and instead use __ffs. Something
  like (assuming we can use bit instead of start)

  if (bit + RADIX_TREE_EXCEPTIONAL_SHIFT < BITS_PER_LONG) {
    tmp = (~(unsigned long)bitmap) >> (bit + RADIX_TREE_EXCEPTIONAL_SHIFT);
    if (tmp) {
      tbit = __ffs(tmp) + bit + RADIX_TREE_EXCEPTIONAL_SHIFT;
      tmp = (unsigned long)bitmap | (1UL << tbit);
      rcu_assign_pointer(*slot, (void *)tmp);
      *id = new + tbit - RADIX_TREE_EXCEPTIONAL_SHIFT;
      return 0;
    }
  }

Rasmus

[toc] | [prev] | [next] | [standalone]

#1546925

From: Rasmus Villemoes [mailto:linux@rasmusvillemoes.dk]
> Nice work! A few random comments/questions:
> 
> - It does add some complexity, but I think a few comments would make it
>   more digestable.

I'm open to adding some comments ... I need some time between writing the code and writing the comments to be sure what comments are useful.

> - Hm, maybe I'm confused, and I certainly don't understand how the whole
>   radix tree works. But do you use every leaf node as an exceptional
>   entry initially, to allocate the first 62 ids from that level? This
>   code

I do!  And that question tells me one useful comment to add!

> 	if ((bit + RADIX_TREE_EXCEPTIONAL_SHIFT) <
> 					BITS_PER_LONG) {
> 		bit += RADIX_TREE_EXCEPTIONAL_SHIFT;
> 		radix_tree_iter_replace(root, &iter, slot,
> 				(void *)((1UL << bit) |
> 				RADIX_TREE_EXCEPTIONAL_ENTRY));
> 		*id = new;
> 		return 0;
> 	}
> 
>    operates on bit, which is the offset from index*IDA_BITMAP_BITS, and
>    it seems to create an exceptional entry somewhere down the tree
>    (which may of course be the root).
> 
>    But we don't seem to allocate another bit from that exceptional entry
>    ever unless it happened to sit at index 0; the code
> 
> 	unsigned long tmp = (unsigned long)bitmap;
> 	if (start < BITS_PER_LONG) {
> 		unsigned tbit = find_next_zero_bit(&tmp,
> 					BITS_PER_LONG, start);
> 		if (tbit < BITS_PER_LONG) {
> 			tmp |= 1UL << tbit;
> 			rcu_assign_pointer(*slot, (void *)tmp);
> 			*id = new + tbit -
> 				RADIX_TREE_EXCEPTIONAL_SHIFT;
> 			return 0;
> 		}
> 	}
> 
>    is only used for small values of start (though it does seem to
>    account for a non-zero value of new == iter.index * IDA_BITMAP_BITS).

Ahh.  You're reading the code wrong, and I wrote the code wrongly too, so it's clearly overly complex.  I was testing with 'start' set to 0, allocating N entries, and then freeing them.  If I'd set start to 1024 and allocated two entries, I'd've seen the failure.

Please see the top commit here ("Improve IDA exceptional entry handling"): http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-12-20


> - In the micro-optimization department, I think we should avoid
>   find_next_zero_bit on a single word, and instead use __ffs. Something
>   like (assuming we can use bit instead of start)
> 
>   if (bit + RADIX_TREE_EXCEPTIONAL_SHIFT < BITS_PER_LONG) {
>     tmp = (~(unsigned long)bitmap) >> (bit + RADIX_TREE_EXCEPTIONAL_SHIFT);
>     if (tmp) {
>       tbit = __ffs(tmp) + bit + RADIX_TREE_EXCEPTIONAL_SHIFT;
>       tmp = (unsigned long)bitmap | (1UL << tbit);
>       rcu_assign_pointer(*slot, (void *)tmp);
>       *id = new + tbit - RADIX_TREE_EXCEPTIONAL_SHIFT;
>       return 0;
>     }
>   }

I'm certainly open to microoptimisations, but I'll have to think about this one for a bit.

[toc] | [prev] | [next] | [standalone]

#1544066

From: Matthew Wilcox
> From: Matthew Wilcox
> > Heh, I was thinking about that too.  The radix tree supports "exceptional
> > entries" which have the bottom bit set.  On a 64-bit machine, we could use
> 62
> > of the bits in the radix tree root to store the ID bitmap.  I'm a little wary of
> the
> > potential complexity, but we should try it out.
> 
> Test patch here: http://git.infradead.org/users/willy/linux-
> dax.git/shortlog/refs/heads/idr-2016-12-16
> It passes the test suite ... which I actually had to adjust because it now succeeds
> in cases where it hadn't (allocating ID 0 without preallocating), and it will now
> fail in cases where it hadn't previously (assuming a single preallocation would
> be enough).  There shouldn't be any examples of that in the kernel proper; it
> was simply me being lazy when I wrote the test suite.

Found a bug, committed a fix (and another test case).  It now no longer returns -EAGAIN in situations where it wouldn't have, so I've reverted that bit of the test suite change.  Still succeeds when it wouldn't have before, but I feel no pressure to change that ;-)

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web