bitmap: Support for pages > BITS_PER_LONG.
Subsystems (2)
PATCH 1/1 bitmap: Support for pages > BITS_PER_LONG.
It seems like I was fortunate enough to trigger the BUG_ON() in the bitmap API regarding pages > BITS_PER_LONG, so as per the comment, here's a stupid implementation which seems to get the job done.
I have an updated store queue API for SH that is currently using this with relative success, and at first glance, it seems like this could be useful for x86 (arch/i386/kernel/pci-dma.c) as well. Particularly for anything using dma_declare_coherent_memory() on large areas and that attempts to allocate large buffers from that space.
The implementation could probably use some work, but it works for me..
---
lib/bitmap.c | 59 ++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 42 insertions(+), 17 deletions(-)
lib/bitmap.c +42 -17
@@ -695,10 +695,11 @@ int bitmap_find_free_region(unsigned lon {unsigned long mask;int pages =1 << order; +int span = (pages + (BITS_PER_LONG -1 )) /BITS_PER_LONG ;int i;if (pages >BITS_PER_LONG ) -return -EINVAL ; + pages =BITS_PER_LONG ;/* make a mask of the order */ mask = (1ul << (pages -1 ));
@@ -708,11 +709,24 @@ int bitmap_find_free_region(unsigned lonfor (i =0 ; i < bits; i += pages) {int index = i/BITS_PER_LONG ;int offset = i - (index *BITS_PER_LONG ); -if ((bitmap[index] & (mask << offset)) ==0 ) { -/* set region in bimap */ - bitmap[index] |= (mask << offset); -return i; - } +int j, space =1 ; + +/* find space in the bitmap */ +for (j =0 ; j < span; j++) +if ((bitmap[index + j] & (mask << offset))) { + space =0 ; +break ; + } + +/* keep looking */ +if (unlikely (!space)) +continue ; + +for (j =0 ; j < span; j++) +/* set region in bitmap */ + bitmap[index + j] |= (mask << offset); + +return i; }return -ENOMEM ; }
@@ -730,30 +744,41 @@ EXPORT_SYMBOL(bitmap_find_free_region);void bitmap_release_region (unsigned long *bitmap,int pos,int order) {int pages =1 << order; -unsigned long mask = (1ul << (pages -1 )); +int span = (pages + (BITS_PER_LONG -1 )) /BITS_PER_LONG ; +unsigned long mask;int index = pos/BITS_PER_LONG ;int offset = pos - (index *BITS_PER_LONG ); +int i; + +if (pages >BITS_PER_LONG ) + pages =BITS_PER_LONG ; + + mask = (1ul << (pages -1 )); mask += mask -1 ; - bitmap[index] &= ~(mask << offset); +for (i =0 ; i < span; i++) + bitmap[index + i] &= ~(mask << offset); }EXPORT_SYMBOL (bitmap_release_region);int bitmap_allocate_region (unsigned long *bitmap,int pos,int order) {int pages =1 << order; -unsigned long mask = (1ul << (pages -1 )); +int span = (pages + (BITS_PER_LONG -1 )) /BITS_PER_LONG ; +unsigned long mask;int index = pos/BITS_PER_LONG ;int offset = pos - (index *BITS_PER_LONG ); +int i; -/* We don't do regions of pages > BITS_PER_LONG. The -* algorithm would be a simple look for multiple zeros in the -* array, but there's no driver today that needs this. If you -* trip this BUG(), you get to code it... */ -BUG_ON (pages >BITS_PER_LONG ); +if (pages >BITS_PER_LONG ) + pages =BITS_PER_LONG ; + + mask = (1ul << (pages -1 )); mask += mask -1 ; -if (bitmap[index] & (mask << offset)) -return -EBUSY ; - bitmap[index] |= (mask << offset); +for (i =0 ; i < span; i++) +if (bitmap[index + i] & (mask << offset)) +return -EBUSY ; +for (i =0 ; i < span; i++) + bitmap[index + i] |= (mask << offset);return 0 ; }EXPORT_SYMBOL (bitmap_allocate_region);
James,
The patch in this lkml thread from Paul Mundt looks to extend the lib/bitmap.c bitmap_find_free_region() and related routines that you added in June 2004. This current patch extends this code to handle more than a page worth of bits.
I added the others to the CC list because they were on your CC list on your patch:
Subject: [PATCH] provide x86 implementation of on-chip coherent memory API
for DMA
From: James Bottomley <[email protected]>
Date: 30 Jun 2004 21:52:24 -0500
Could you look Mundt's patch, and see if it looks ok?
Thanks.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.925.600.0401Quoted 1 line · Paul Jackson
Could you look Mundt's patch, and see if it looks ok?
Not being on lkml, this was harder than it sounds, but I eventually found the actual patch on marc. However, no, it doesn't look right.
This:
lib/bitmap.c int bitmap_find_free_region(unsigned lon · line 716
Quoted 3 lines
lib/bitmap.c +3
-0+/* find space in the bitmap */ +for (j =0 ; j < span; j++) +if ((bitmap[index + j] & (mask << offset))) {
Is wrong. You're looking for an unset span of order bits at a given offset. So you get the byte offset for the first, then all the following bitmap[n] need to be zero until you need to do an offset in reverse for the last bit. i.e. (assuming BITS_PER_LONG=32) for a span of 126 at offset 1, you check
bitmap[0] & 0xfffffffe == 0
bitmap[1] & 0xffffffff == 0
bitmap[2] & 0xffffffff == 0
bitmap[3] & 0x7fffffff == 0
and so on.
lib/bitmap.c int bitmap_find_free_region(unsigned lon · line 727
Quoted 11 lines
lib/bitmap.c +11
-0+ space =0 ; +break ; + } + +/* keep looking */ +if (unlikely (!space)) +continue ; + +for (j =0 ; j < span; j++) +/* set region in bitmap */ + bitmap[index + j] |= (mask << offset);
Likewise, you'd have to or in what you checked above.
James
Quoted 19 lines · James Bottomley
Quoted 1 line · Paul Jackson
Could you look Mundt's patch, and see if it looks ok?
Not being on lkml, this was harder than it sounds, but I eventually found the actual patch on marc. However, no, it doesn't look right.
This:
lib/bitmap.c int bitmap_find_free_region(unsigned lon · line 716
Quoted 3 lines
lib/bitmap.c +3
-0+/* find space in the bitmap */ +for (j =0 ; j < span; j++) +if ((bitmap[index + j] & (mask << offset))) {Is wrong. You're looking for an unset span of order bits at a given offset. So you get the byte offset for the first, then all the following bitmap[n] need to be zero until you need to do an offset in reverse for the last bit. i.e. (assuming BITS_PER_LONG=32) for a span of 126 at offset 1, you check
Quoted 7 lines
bitmap[0] &
0xfffffffe== 0
bitmap[1] &0xffffffff== 0
bitmap[2] &0xffffffff== 0
bitmap[3] &0x7fffffff== 0and so on.
This code operates on the assumption that offset is always 0 for the pages == BITS_PER_LONG case. It's calculated in this order:
unsigned int pages = 1 << order;
int i;
int span = (pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
if (pages > BITS_PER_LONG)
pages = BITS_PER_LONG;...
for (i = 0; i < bits; i += pages) {
int index = i/BITS_PER_LONG;
int offset = i - (index * BITS_PER_LONG);...
So in the case of pages >= BITS_PER_LONG the mask will be 0xffffffff, and offset will be 0, and the span will define how many adjacent words we need to set. Unless I'm missing something, I don't see how your case would happen. I did test this quite a bit mixing both tiny and large orders.
Quoted 2 lines · James
Is wrong. You're looking for an unset span of order bits at a given offset.
But your comment, James, said:
* This is used to allocate a memory region from a bitmap. The idea is
* that the region has to be 1<<order sized and 1<<order aligned (this
* makes the search algorithm much faster).
Quoted 2 lines · like the other Paul
Unless I'm missing something, I don't see how your case would happen.
Quoted 2 lines · James further
i.e. (assuming BITS_PER_LONG=32) for a span
of 126 at offset 1, you check
I thought that the span had to be a power of two. Perhaps you mean 128, not 126 (order 7: 2**7 == 128).
And I thought, from your comment above, that if the span was 128, then the alignment had to be 128 as well.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.925.600.0401It looks to me like I never properly reviewed James patch when it was originally submitted. It has some minor confusions that have gotten slightly worse with this patch.
Just reading the patch, I see the following possible opportunities for improvement:
* Could the calculation of mask:
mask = (1ul << (pages - 1));
mask += mask - 1;
be simplified to:
mask = (1UL << pages) - 1;(and note that 1UL is easier to read than 1ul)
* The variable named 'pages' is misnamed. It happens that the current user of this code is using one bit to represent one page, but that is not something that this code has any business knowing. For this code, it might better be 'nbits' or some such.
* With your 'pages > BITS_PER_LONG' patch, this 'pages' variable becomes more confused. Apparently, it is the number of bits to consider in each word scanned, and 'scan' is the number of words to scan. Hmmm ... that's not quite right either. It seems that 'pages' is first set (in bitmask_find_free_region) to the number of bits total to find, which value is used to compute 'scan', the number of words needed to hold that many bits; then 'pages' is recomputed to be the number of bits in a single word to examine, which value is used to compute the 'mask'. This sort of dual use of a poorly named variable is confusing. I'd suggest two variables - 'nbitstotal' and 'nbitsinword', or some such. Or short variable names, and a comment:
int bt; /* total number of bits to find free */
int bw; /* how many bits to consider in one word */
* The block comment states:
allocate a memory region from a bitmap
This is another confusion between the user of this code, and this current code. I think we are allocating a sequence of consecutive bits of size and allignment some power of two ('order' is that power), not allocating a 'memory region.'
* There is no function block comment for bitmap_allocate_region().
* The include/linux/bitmap.h header comment is missing the three lines specifying these three routines.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.925.600.0401Someone unnamed has suggested I submit a patch with these cleanups.
But I am lazy git who hates to test code, and it looks like Paul Mundt is in a position to actually test that whatever we end up with still works.
So I intend to send in two totally untested patches shortly:
1) some minor cleanups of these bitmap routines, and
2) Mundt's > BITS_PER_LONG patch, more or less, on top of that.
Then perhaps Mundt could retest and fix what I broke, then send in a final pair of patches for Andrew's consideration.
If this isn't such a hot idea, Mundt, holler, and we can work something else out.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.925.600.0401