1/1: Device-Mapper: Remove 1024 devices limitation

Remove the limitation of 1024 DM devices.

Quoted 1 line · Kevin Corry

Remove the limitation of 1024 DM devices.

That seems to be an awful lot of fuss just to maintain a bitmap.

What is a realistic useful upper bound on the minors? Would it not be sufficient to increase the size of the statically allocated bitmap?

Did you consider going to a different data structure altogether? lib/radix-tree.c and lib/idr.c provide appropriate ones.

Quoted 3 lines

Did you consider going to a different data structure altogether? lib/radix-tree.c and lib/idr.c provide appropriate ones.

The idr stuff looks promising at first glance. I'll take a better look at it tomorrow and see if we can switch from a bit-set to one of these data structures.

Quoted 7 lines · Kevin Corry

Quoted 3 lines

Did you consider going to a different data structure altogether?

lib/radix-tree.c and lib/idr.c provide appropriate ones.

The idr stuff looks promising at first glance. I'll take a better look
at it tomorrow and see if we can switch from a bit-set to one of these data structures.

Yes, idr is the one to use. That linear search you have in there becomes logarithmic. Will speed up the registration of 100,000 minors no end ;)

Quoted 3 lines

Yes, idr is the one to use. That linear search you have in there becomes logarithmic. Will speed up the registration of 100,000 minors no end ;)

I've got a patch that switches from a bit-set to an IDR structure. The only thing I'm slightly uncertain about is the case where we're trying to create a device with a specific minor number (when creating a DM device, you have the choice to specify a minor number or have DM find the first available one). To do this, I call idr_find() with the desired minor. If that returns NULL (meaning it's not already in use), then I call idr_get_new_above() with that same desired minor. In the cases I've tested, this always chooses the desired minor, but can we depend on that behavior?

Quoted 6 lines · Kevin Corry

Quoted 5 lines

Yes, idr is the one to use. That linear search you have in there becomes

logarithmic. Will speed up the registration of 100,000 minors no end ;)

Quoted 9 lines

I've got a patch that switches from a bit-set to an IDR structure. The
only thing I'm slightly uncertain about is the case where we're trying to create a device with a specific minor number (when creating a DM device, you have the choice to specify a minor number or have DM find the first available one). To do this, I call idr_find() with the desired minor. If that returns NULL (meaning it's not already in use), then I call idr_get_new_above() with that same desired minor. In the cases I've tested, this always chooses the desired minor, but can we depend on that behavior?

Yes, that has to work - you're holding the lock throughout.

It would be sensible to make that a part of the idr API though.

After talking with Alasdair a bit, there might be one bug in the "dm-use-idr" patch I submitted before. It seems (based on some comments in lib/idr.c) that the idr_find() routine might not return NULL if the desired ID value is not in the tree.

Quoted 1 line · Kevin Corry

It seems (based on some comments in lib/idr.c) that

Confused. idr_find() returns the thing it found, or NULL.

To which comments do you refer?

Yes, but the comments imply that the thing it found might in some circumstances not be the thing you asked it to look for

Quoted 2 lines

Confused. idr_find() returns the thing it found, or NULL.

Yes, but the comments imply that the thing it found might in some circumstances not be the thing you asked it to look for (if there've been deletions) and it's the caller's responsibility to verify what's returned.

Quoted 1 line

To which comments do you refer?

lib/idr.c:30

* What you need to do is, since we don't keep the counter as part of
* id / ptr pair, to keep a copy of it in the pointed to structure
* (or else where) so that when you ask for a ptr you can varify that
* the returned ptr is correct by comparing the id it contains with the one
* you asked for. In other words, we only did half the reuse protection.
* Since the code depends on your code doing this check, we ignore high
* order bits in the id, not just the count, but bits that would, if used,
* index outside of the allocated ids. In other words, if the largest id
* currently allocated is 32 a look up will only look at the low 5 bits of
* the id. Since you will want to keep this id in the structure anyway
* (if for no other reason than to be able to eliminate the id when the
* structure is found in some other way) this seems reasonable. If you
* really think otherwise, the code to check these bits here, it is just
* disabled with a #if 0.

Quoted 5 lines · Kevin Corry

After talking with Alasdair a bit, there might be one bug in the "dm-use-idr" patch I submitted before. It seems (based on some comments in lib/idr.c) that the idr_find() routine might not return NULL if the desired ID value is not in the tree.

Confused. idr_find() returns the thing it found, or NULL. To which comments do you refer?

Quoted 10 lines · Andrew Morton

Quoted 5 lines · Kevin Corry

After talking with Alasdair a bit, there might be one bug in the "dm-use-idr" patch I submitted before. It seems (based on some comments in lib/idr.c) that the idr_find() routine might not return NULL if the desired ID value is not in the tree.

Confused. idr_find() returns the thing it found, or NULL. To which comments do you refer?

Hi Andrew, Kevin,

Kevin is correct. It's more of the nonsense related to having a counter in the upper bits of the id. If you call idr_find with an id that is beyond the currently allocated space it ignores the upper bits and returns one of the entries that is in the allocated space. This aliasing is most annoying.

I'm attaching an untested patch which removes the counter in the upper bits of the id and makes idr_find return NULL if the requested id is beyond the allocated space.

I suspect that there are problems with
id values which are less than zero.

Quoted 13 lines · Jim Houston

Quoted 10 lines · Andrew Morton

Quoted 5 lines · Kevin Corry

After talking with Alasdair a bit, there might be one bug in the "dm-use-idr" patch I submitted before. It seems (based on some comments in lib/idr.c) that the idr_find() routine might not return NULL if the desired ID value is not in the tree.

Confused. idr_find() returns the thing it found, or NULL. To which comments do you refer?

Quoted 7 lines

Hi Andrew, Kevin,

Kevin is correct. It's more of the nonsense related to having a counter in the upper bits of the id. If you call idr_find with an id that is beyond the currently allocated space it ignores the upper bits and returns one of the entries that is in the allocated space. This aliasing is most annoying.

erk, OK, we have vestigial bits still. Note that MAX_ID_SHIFT is now 31 on 32-bit, so we're still waggling the top bit.

Quoted 3 lines

I'm attaching an untested patch which removes the counter in the upper bits of the id and makes idr_find return NULL if the requested id is beyond the allocated space.

Would you have time to get it tested please?

Quoted 2 lines

I suspect that there are problems with
id values which are less than zero.

Me too. I'd only be confident in the 0..2G range.

idr.c line 325

Quoted 7 lines

idr.c renamed from idr.c.orig +2 -1

-#endif
+	if (id >= (1 << n))
+		return NULL;
 	while (n > 0 && p) {
 		n -= IDR_BITS;
 		p = p->ary[(id >> n) & IDR_MASK];

I think the above test is unneeded?

With out the test above an id beyond the allocated space will alias to one that exists. Perhaps the highest id currently allocated is 100, there will be two layers in the radix tree and the while loop above will only look at the 10 least significant bits. If you call idr_find with 1025 it will return the pointer associated with id 1.

The patch I sent was against linux-2.6.7, so I missed the change to MAX_ID_SHIFT.

Quoted 6 lines

With out the test above an id beyond the allocated space will alias to one that exists. Perhaps the highest id currently allocated is 100, there will be two layers in the radix tree and the while loop above will only look at the 10 least significant bits. If you call idr_find with 1025 it will return the pointer associated with id 1.

OK.

Quoted 2 lines

The patch I sent was against linux-2.6.7, so I missed the change to MAX_ID_SHIFT.

How about this?

Quoted 15 lines · On Tue, 2004-07-06 at 19:16, Andrew Morton wrote: Jim Houston…

Quoted 6 lines

With out the test above an id beyond the allocated space will alias to one that exists. Perhaps the highest id currently allocated is 100, there will be two layers in the radix tree and the while loop above will only look at the 10 least significant bits. If you call idr_find with 1025 it will return the pointer associated with id 1.

OK.

Quoted 2 lines

The patch I sent was against linux-2.6.7, so I missed the change to MAX_ID_SHIFT.

How about this?

lib/idr.c void *idr_find(struct idr *idp, int id) · line 364

Quoted 8 lines

lib/idr.c renamed from lib/idr.c~idr-stale-comment +4 -0

 	n = idp->layers * IDR_BITS;
+	if (id >= (1 << n))
+		return NULL;
+
 	p = idp->top;
+
 	/* Mask off upper bits we don't use for the search. */
 	id &= MAX_ID_MASK;

Hi Andrew,

It's not quite right. If you want to keep a count in the upper bits you have to mask off that count before checking if the id is beyond the end of the allocated space.

Quoted 6 lines · Jim Houston

Hi Andrew,

It's not quite right. If you want to keep a count in the upper bits you have to mask off that count before checking if the id is beyond the end of the allocated space.

OK, I'll fix that up.

But I don't want to keep a count in the upper bits! I want rid of that stuff altogether, completely, all of it. It just keeps on hanging around :(

We should remove MAX_ID_* from the kernel altogether.

Quoted 14 lines · Andrew Morton

Quoted 6 lines · Jim Houston

Hi Andrew,

It's not quite right. If you want to keep a count in the upper bits you have to mask off that count before checking if the id is beyond the end of the allocated space.

OK, I'll fix that up.

But I don't want to keep a count in the upper bits! I want rid of that stuff altogether, completely, all of it. It just keeps on hanging around :(

Quoted 1 line

We should remove MAX_ID_* from the kernel altogether.

Just following up on the proposed IDR changes. Based on the patches in the latest -mm tree, I'm assuming there is or will be a fix for IDR so it will always return NULL when asked to find an id that's not currently allocated. Is this correct? If so, I can drop the second "dm-use-idr" patch (from July 6, 2004) and keep the one that's currently in -mm.