|
Linux Kernel
3.7.1
|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
|
Linux Kernel
3.7.1
|
#include <linux/export.h>#include <linux/thread_info.h>#include <linux/ctype.h>#include <linux/errno.h>#include <linux/bitmap.h>#include <linux/bitops.h>#include <linux/bug.h>#include <asm/uaccess.h>Go to the source code of this file.
Macros | |
| #define | CHUNKSZ 32 |
| #define | nbits_to_hold_value(val) fls(val) |
| #define | BASEDEC 10 /* fancier cpuset lists input in decimal */ |
Enumerations | |
| enum | { REG_OP_ISFREE, REG_OP_ALLOC, REG_OP_RELEASE } |
| anonymous enum |
| int __bitmap_parse | ( | const char * | buf, |
| unsigned int | buflen, | ||
| int | is_user, | ||
| unsigned long * | maskp, | ||
| int | nmaskbits | ||
| ) |
__bitmap_parse - convert an ASCII hex string into a bitmap. : pointer to buffer containing string. : buffer size in bytes. If string is smaller than this then it must be terminated with a \0. : location of buffer, 0 indicates kernel space : pointer to bitmap array that will contain result. : size of bitmap, in bits.
Commas group hex digits into chunks. Each chunk defines exactly 32 bits of the resultant bitmask. No chunk may specify a value larger than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value then leading 0-bits are prepended. %-EINVAL is returned for illegal characters and for grouping errors such as "1,,5", ",44", "," and "". Leading and trailing whitespace accepted, but not embedded whitespace.
__bitmap_shift_left - logical left shift of the bits in a bitmap : destination bitmap : source bitmap : shift by this many bits : bitmap size, in bits
Shifting left (multiplying) means moving bits in the LS -> MS direction. Zeros are fed into the vacated LS bit positions and those MS bits shifted off the top are lost.
__bitmap_shift_right - logical right shift of the bits in a bitmap : destination bitmap : source bitmap : shift by this many bits : bitmap size, in bits
Shifting right (dividing) means moving bits in the MS -> LS bit direction. Zeros are fed into the vacated MS positions and the LS bits shifted off the bottom are lost.
bitmap_allocate_region - allocate bitmap region : array of unsigned longs corresponding to the bitmap : beginning of bit region to allocate : region size (log base 2 of number of bits) to allocate
Allocate (set bits in) a specified region of a bitmap.
Return 0 on success, or %-EBUSY if specified region wasn't free (not all bits were zero).
bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit : bit position to be mapped : defines domain of map : defines range of map : number of bits in each of these bitmaps
Let and define a mapping of bit positions, such that whatever position is held by the n-th set bit in is mapped to the n-th set bit in . In the more general case, allowing for the possibility that the weight 'w' of is less than the weight of , map the position of the n-th set bit in to the position of the m-th set bit in , where m == n % w.
The positions of unset bits in are mapped to themselves (the identify map).
Apply the above specified mapping to bit position , returning the new bit position.
For example, lets say that has bits 4 through 7 set, and has bits 12 through 15 set. This defines the mapping of bit position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other bit positions unchanged. So if say is 5, then this routine returns 13.
bitmap_find_free_region - find a contiguous aligned mem region : array of unsigned longs corresponding to the bitmap : number of bits in the bitmap : region size (log base 2 of number of bits) to find
Find a region of free (zero) bits in a of bits and allocate them (set them to one). Only consider regions of length a power () of two, aligned to that power of two, which makes the search algorithm much faster.
Return the bit offset in bitmap of the allocated region, or -errno on failure.
bitmap_fold - fold larger bitmap into smaller, modulo specified size : resulting smaller bitmap : original larger bitmap : specified size : number of bits in each of these bitmaps
For each bit oldbit in , set bit oldbit mod in . Clear all other bits in . See further the comment and Example [2] for bitmap_onto() for why and how to use this.
| void bitmap_onto | ( | unsigned long * | dst, |
| const unsigned long * | orig, | ||
| const unsigned long * | relmap, | ||
| int | bits | ||
| ) |
bitmap_onto - translate one bitmap relative to another : resulting translated bitmap : original untranslated bitmap : bitmap relative to which translated : number of bits in each of these bitmaps
Set the n-th bit of iff there exists some m such that the n-th bit of is set, the m-th bit of is set, and the n-th bit of is also the m-th set bit of . (If you understood the previous sentence the first time your read it, you're overqualified for your current job.)
In other words, is mapped onto (surjectively) , using the the map { <n, m> | the n-th bit of is the m-th set bit of }.
Any set bits in above bit number W, where W is the weight of (number of set bits in) are mapped nowhere. In particular, if for all bits m set in , m >= W, then will end up empty. In situations where the possibility of such an empty result is not desired, one way to avoid it is to use the bitmap_fold() operator, below, to first fold the bitmap over itself so that all its set bits x are in the range 0 <= x < W. The bitmap_fold() operator does this by setting the bit (m % W) in , for each bit (m) set in .
Example [1] for bitmap_onto(): Let's say has bits 30-39 set, and has bits 1, 3, 5, 7, 9 and 11 set. Then on return from this routine, will have bits 31, 33, 35, 37 and 39 set.
When bit 0 is set in , it means turn on the bit in corresponding to whatever is the first bit (if any) that is turned on in . Since bit 0 was off in the above example, we leave off that bit (bit 30) in .
When bit 1 is set in (as in the above example), it means turn on the bit in corresponding to whatever is the second bit that is turned on in . The second bit in that was turned on in the above example was bit 31, so we turned on bit 31 in .
Similarly, we turned on bits 33, 35, 37 and 39 in , because they were the 4th, 6th, 8th and 10th set bits set in , and the 4th, 6th, 8th and 10th bits of (i.e. bits 3, 5, 7 and 9) were also set.
When bit 11 is set in , it means turn on the bit in corresponding to whatever is the twelfth bit that is turned on in . In the above example, there were only ten bits turned on in (30..39), so that bit 11 was set in had no affect on .
Example [2] for bitmap_fold() + bitmap_onto(): Let's say has these ten bits set: 40 41 42 43 45 48 53 61 74 95 (for the curious, that's 40 plus the first ten terms of the Fibonacci sequence.)
Further lets say we use the following code, invoking bitmap_fold() then bitmap_onto, as suggested above to avoid the possitility of an empty result:
unsigned long *tmp; // a temporary bitmap's bits
bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits); bitmap_onto(dst, tmp, relmap, bits);
Then this table shows what various values of would be, for various 's. I list the zero-based positions of each set bit. The tmp column shows the intermediate result, as computed by using bitmap_fold() to fold the bitmap modulo ten (the weight of ).
@orig tmp @dst 0 0 40 1 1 41 9 9 95 10 0 40 (*) 1 3 5 7 1 3 5 7 41 43 48 61 0 1 2 3 4 0 1 2 3 4 40 41 42 43 45 0 9 18 27 0 9 8 7 40 61 74 95 0 10 20 30 0 40 0 11 22 33 0 1 2 3 40 41 42 43 0 12 24 36 0 2 4 6 40 42 45 53 78 102 211 1 2 8 41 42 74 (*)
(*) For these marked lines, if we hadn't first done bitmap_fold() into tmp, then the result would have been empty.
If either of or is empty (no set bits), then will be returned empty.
If (as explained above) the only set bits in are in positions m where m >= W, (where W is the weight of ) then will once again be returned empty.
All bits in not set by the above rule are cleared.
bitmap_ord_to_pos - find position of n-th set bit in bitmap : pointer to bitmap : ordinal bit position (n-th set bit, n >= 0) : number of valid bit positions in
Map the ordinal offset of bit in to its position in . Value of should be in range 0 <= < weight(buf), else results are undefined.
If for example, just bits 4 through 7 are set in , then values 0 through 3 will get mapped to 4 through 7, respectively, and all other values return undefined values. When value 3 gets mapped to (returns) value 7 in this example, that means that the 3rd set bit (starting with 0th) is at position 7 in .
The bit positions 0 through are valid positions in .
| int bitmap_parse_user | ( | const char __user * | ubuf, |
| unsigned int | ulen, | ||
| unsigned long * | maskp, | ||
| int | nmaskbits | ||
| ) |
bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
: pointer to user buffer containing string. : buffer size in bytes. If string is smaller than this then it must be terminated with a \0. : pointer to bitmap array that will contain result. : size of bitmap, in bits.
Wrapper for __bitmap_parse(), providing it with user buffer.
We cannot have this as an inline function in bitmap.h because it needs linux/uaccess.h to get the access_ok() declaration and this causes cyclic dependencies.
| int bitmap_parselist_user | ( | const char __user * | ubuf, |
| unsigned int | ulen, | ||
| unsigned long * | maskp, | ||
| int | nmaskbits | ||
| ) |
: pointer to user buffer containing string. : buffer size in bytes. If string is smaller than this then it must be terminated with a \0. : pointer to bitmap array that will contain result. : size of bitmap, in bits.
Wrapper for bitmap_parselist(), providing it with user buffer.
We cannot have this as an inline function in bitmap.h because it needs linux/uaccess.h to get the access_ok() declaration and this causes cyclic dependencies.
bitmap_release_region - release allocated bitmap region : array of unsigned longs corresponding to the bitmap : beginning of bit region to release : region size (log base 2 of number of bits) to release
This is the complement to __bitmap_find_free_region() and releases the found region (by clearing it in the bitmap).
No return value.
| void bitmap_remap | ( | unsigned long * | dst, |
| const unsigned long * | src, | ||
| const unsigned long * | old, | ||
| const unsigned long * | new, | ||
| int | bits | ||
| ) |
bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap : remapped result : subset to be remapped : defines domain of map : defines range of map : number of bits in each of these bitmaps
Let and define a mapping of bit positions, such that whatever position is held by the n-th set bit in is mapped to the n-th set bit in . In the more general case, allowing for the possibility that the weight 'w' of is less than the weight of , map the position of the n-th set bit in to the position of the m-th set bit in , where m == n % w.
If either of the and bitmaps are empty, or if and point to the same location, then this routine copies to .
The positions of unset bits in are mapped to themselves (the identify map).
Apply the above specified mapping to , placing the result in , clearing any bits previously set in .
For example, lets say that has bits 4 through 7 set, and has bits 12 through 15 set. This defines the mapping of bit position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other bit positions unchanged. So if say comes into this routine with bits 1, 5 and 7 set, then should leave with bits 1, 13 and 15 set.
| int bitmap_scnlistprintf | ( | char * | buf, |
| unsigned int | buflen, | ||
| const unsigned long * | maskp, | ||
| int | nmaskbits | ||
| ) |
bitmap_scnlistprintf - convert bitmap to list format ASCII string : byte buffer into which string is placed : reserved size of , in bytes : pointer to bitmap to convert : size of bitmap, in bits
Output format is a comma-separated list of decimal numbers and ranges. Consecutively set bits are shown as two hyphen-separated decimal numbers, the smallest and largest bit numbers set in the range. Output format is compatible with the format accepted as input by bitmap_parselist().
The return value is the number of characters which were written to *buf excluding the trailing '\0', as per ISO C99's scnprintf.
| int bitmap_scnprintf | ( | char * | buf, |
| unsigned int | buflen, | ||
| const unsigned long * | maskp, | ||
| int | nmaskbits | ||
| ) |
bitmap_scnprintf - convert bitmap to an ASCII hex string. : byte buffer into which string is placed : reserved size of , in bytes : pointer to bitmap to convert : size of bitmap, in bits
Exactly bits are displayed. Hex digits are grouped into comma-separated sets of eight digits per set. Returns the number of characters which were written to *buf, excluding the trailing \0.
| EXPORT_SYMBOL | ( | __bitmap_empty | ) |
| EXPORT_SYMBOL | ( | __bitmap_full | ) |
| EXPORT_SYMBOL | ( | __bitmap_equal | ) |
| EXPORT_SYMBOL | ( | __bitmap_complement | ) |
| EXPORT_SYMBOL | ( | __bitmap_shift_right | ) |
| EXPORT_SYMBOL | ( | __bitmap_shift_left | ) |
| EXPORT_SYMBOL | ( | __bitmap_and | ) |
| EXPORT_SYMBOL | ( | __bitmap_or | ) |
| EXPORT_SYMBOL | ( | __bitmap_xor | ) |
| EXPORT_SYMBOL | ( | __bitmap_andnot | ) |
| EXPORT_SYMBOL | ( | __bitmap_intersects | ) |
| EXPORT_SYMBOL | ( | __bitmap_subset | ) |
| EXPORT_SYMBOL | ( | __bitmap_weight | ) |
| EXPORT_SYMBOL | ( | bitmap_set | ) |
| EXPORT_SYMBOL | ( | bitmap_clear | ) |
| EXPORT_SYMBOL | ( | bitmap_find_next_zero_area | ) |
| EXPORT_SYMBOL | ( | bitmap_scnprintf | ) |
| EXPORT_SYMBOL | ( | __bitmap_parse | ) |
| EXPORT_SYMBOL | ( | bitmap_parse_user | ) |
| EXPORT_SYMBOL | ( | bitmap_scnlistprintf | ) |
| EXPORT_SYMBOL | ( | bitmap_parselist | ) |
| EXPORT_SYMBOL | ( | bitmap_parselist_user | ) |
| EXPORT_SYMBOL | ( | bitmap_remap | ) |
| EXPORT_SYMBOL | ( | bitmap_bitremap | ) |
| EXPORT_SYMBOL | ( | bitmap_onto | ) |
| EXPORT_SYMBOL | ( | bitmap_fold | ) |
| EXPORT_SYMBOL | ( | bitmap_find_free_region | ) |
| EXPORT_SYMBOL | ( | bitmap_release_region | ) |
| EXPORT_SYMBOL | ( | bitmap_allocate_region | ) |
| EXPORT_SYMBOL | ( | bitmap_copy_le | ) |
1.8.2