Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Macros | Enumerations | Functions
bitmap.c File Reference
#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 }
 

Functions

int __bitmap_empty (const unsigned long *bitmap, int bits)
 
 EXPORT_SYMBOL (__bitmap_empty)
 
int __bitmap_full (const unsigned long *bitmap, int bits)
 
 EXPORT_SYMBOL (__bitmap_full)
 
int __bitmap_equal (const unsigned long *bitmap1, const unsigned long *bitmap2, int bits)
 
 EXPORT_SYMBOL (__bitmap_equal)
 
void __bitmap_complement (unsigned long *dst, const unsigned long *src, int bits)
 
 EXPORT_SYMBOL (__bitmap_complement)
 
void __bitmap_shift_right (unsigned long *dst, const unsigned long *src, int shift, int bits)
 
 EXPORT_SYMBOL (__bitmap_shift_right)
 
void __bitmap_shift_left (unsigned long *dst, const unsigned long *src, int shift, int bits)
 
 EXPORT_SYMBOL (__bitmap_shift_left)
 
int __bitmap_and (unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits)
 
 EXPORT_SYMBOL (__bitmap_and)
 
void __bitmap_or (unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits)
 
 EXPORT_SYMBOL (__bitmap_or)
 
void __bitmap_xor (unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits)
 
 EXPORT_SYMBOL (__bitmap_xor)
 
int __bitmap_andnot (unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits)
 
 EXPORT_SYMBOL (__bitmap_andnot)
 
int __bitmap_intersects (const unsigned long *bitmap1, const unsigned long *bitmap2, int bits)
 
 EXPORT_SYMBOL (__bitmap_intersects)
 
int __bitmap_subset (const unsigned long *bitmap1, const unsigned long *bitmap2, int bits)
 
 EXPORT_SYMBOL (__bitmap_subset)
 
int __bitmap_weight (const unsigned long *bitmap, int bits)
 
 EXPORT_SYMBOL (__bitmap_weight)
 
void bitmap_set (unsigned long *map, int start, int nr)
 
 EXPORT_SYMBOL (bitmap_set)
 
void bitmap_clear (unsigned long *map, int start, int nr)
 
 EXPORT_SYMBOL (bitmap_clear)
 
unsigned long bitmap_find_next_zero_area (unsigned long *map, unsigned long size, unsigned long start, unsigned int nr, unsigned long align_mask)
 
 EXPORT_SYMBOL (bitmap_find_next_zero_area)
 
int bitmap_scnprintf (char *buf, unsigned int buflen, const unsigned long *maskp, int nmaskbits)
 
 EXPORT_SYMBOL (bitmap_scnprintf)
 
int __bitmap_parse (const char *buf, unsigned int buflen, int is_user, unsigned long *maskp, int nmaskbits)
 
 EXPORT_SYMBOL (__bitmap_parse)
 
int bitmap_parse_user (const char __user *ubuf, unsigned int ulen, unsigned long *maskp, int nmaskbits)
 
 EXPORT_SYMBOL (bitmap_parse_user)
 
int bitmap_scnlistprintf (char *buf, unsigned int buflen, const unsigned long *maskp, int nmaskbits)
 
 EXPORT_SYMBOL (bitmap_scnlistprintf)
 
int bitmap_parselist (const char *bp, unsigned long *maskp, int nmaskbits)
 
 EXPORT_SYMBOL (bitmap_parselist)
 
int bitmap_parselist_user (const char __user *ubuf, unsigned int ulen, unsigned long *maskp, int nmaskbits)
 
 EXPORT_SYMBOL (bitmap_parselist_user)
 
int bitmap_ord_to_pos (const unsigned long *buf, int ord, int bits)
 
void bitmap_remap (unsigned long *dst, const unsigned long *src, const unsigned long *old, const unsigned long *new, int bits)
 
 EXPORT_SYMBOL (bitmap_remap)
 
int bitmap_bitremap (int oldbit, const unsigned long *old, const unsigned long *new, int bits)
 
 EXPORT_SYMBOL (bitmap_bitremap)
 
void bitmap_onto (unsigned long *dst, const unsigned long *orig, const unsigned long *relmap, int bits)
 
 EXPORT_SYMBOL (bitmap_onto)
 
void bitmap_fold (unsigned long *dst, const unsigned long *orig, int sz, int bits)
 
 EXPORT_SYMBOL (bitmap_fold)
 
int bitmap_find_free_region (unsigned long *bitmap, int bits, int order)
 
 EXPORT_SYMBOL (bitmap_find_free_region)
 
void bitmap_release_region (unsigned long *bitmap, int pos, int order)
 
 EXPORT_SYMBOL (bitmap_release_region)
 
int bitmap_allocate_region (unsigned long *bitmap, int pos, int order)
 
 EXPORT_SYMBOL (bitmap_allocate_region)
 
void bitmap_copy_le (void *dst, const unsigned long *src, int nbits)
 
 EXPORT_SYMBOL (bitmap_copy_le)
 

Macro Definition Documentation

#define BASEDEC   10 /* fancier cpuset lists input in decimal */

Definition at line 362 of file bitmap.c.

#define CHUNKSZ   32

Definition at line 360 of file bitmap.c.

#define nbits_to_hold_value (   val)    fls(val)

Definition at line 361 of file bitmap.c.

Enumeration Type Documentation

anonymous enum
Enumerator:
REG_OP_ISFREE 
REG_OP_ALLOC 
REG_OP_RELEASE 

Definition at line 1043 of file bitmap.c.

Function Documentation

int __bitmap_and ( unsigned long dst,
const unsigned long bitmap1,
const unsigned long bitmap2,
int  bits 
)

Definition at line 184 of file bitmap.c.

int __bitmap_andnot ( unsigned long dst,
const unsigned long bitmap1,
const unsigned long bitmap2,
int  bits 
)

Definition at line 219 of file bitmap.c.

void __bitmap_complement ( unsigned long dst,
const unsigned long src,
int  bits 
)

Definition at line 89 of file bitmap.c.

int __bitmap_empty ( const unsigned long bitmap,
int  bits 
)

Definition at line 43 of file bitmap.c.

int __bitmap_equal ( const unsigned long bitmap1,
const unsigned long bitmap2,
int  bits 
)

Definition at line 73 of file bitmap.c.

int __bitmap_full ( const unsigned long bitmap,
int  bits 
)

Definition at line 58 of file bitmap.c.

int __bitmap_intersects ( const unsigned long bitmap1,
const unsigned long bitmap2,
int  bits 
)

Definition at line 232 of file bitmap.c.

void __bitmap_or ( unsigned long dst,
const unsigned long bitmap1,
const unsigned long bitmap2,
int  bits 
)

Definition at line 197 of file bitmap.c.

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.

Definition at line 419 of file bitmap.c.

void __bitmap_shift_left ( unsigned long dst,
const unsigned long src,
int  shift,
int  bits 
)

__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.

Definition at line 156 of file bitmap.c.

void __bitmap_shift_right ( unsigned long dst,
const unsigned long src,
int  shift,
int  bits 
)

__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.

Definition at line 111 of file bitmap.c.

int __bitmap_subset ( const unsigned long bitmap1,
const unsigned long bitmap2,
int  bits 
)

Definition at line 247 of file bitmap.c.

int __bitmap_weight ( const unsigned long bitmap,
int  bits 
)

Definition at line 262 of file bitmap.c.

void __bitmap_xor ( unsigned long dst,
const unsigned long bitmap1,
const unsigned long bitmap2,
int  bits 
)

Definition at line 208 of file bitmap.c.

int bitmap_allocate_region ( unsigned long bitmap,
int  pos,
int  order 
)

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).

Definition at line 1157 of file bitmap.c.

int bitmap_bitremap ( int  oldbit,
const unsigned long old,
const unsigned long new,
int  bits 
)

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.

Definition at line 859 of file bitmap.c.

void bitmap_clear ( unsigned long map,
int  start,
int  nr 
)

Definition at line 297 of file bitmap.c.

void bitmap_copy_le ( void dst,
const unsigned long src,
int  nbits 
)

bitmap_copy_le - copy a bitmap, putting the bits into little-endian order. : destination buffer : bitmap to copy : number of bits in the bitmap

Require nbits % BITS_PER_LONG == 0.

Definition at line 1174 of file bitmap.c.

int bitmap_find_free_region ( unsigned long bitmap,
int  bits,
int  order 
)

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.

Definition at line 1115 of file bitmap.c.

unsigned long bitmap_find_next_zero_area ( unsigned long map,
unsigned long  size,
unsigned long  start,
unsigned int  nr,
unsigned long  align_mask 
)

Definition at line 330 of file bitmap.c.

void bitmap_fold ( unsigned long dst,
const unsigned long orig,
int  sz,
int  bits 
)

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.

Definition at line 1011 of file bitmap.c.

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.

Definition at line 971 of file bitmap.c.

int bitmap_ord_to_pos ( const unsigned long buf,
int  ord,
int  bits 
)

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 .

Definition at line 761 of file bitmap.c.

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.

Definition at line 504 of file bitmap.c.

int bitmap_parselist ( const char bp,
unsigned long maskp,
int  nmaskbits 
)

Definition at line 665 of file bitmap.c.

int bitmap_parselist_user ( const char __user ubuf,
unsigned int  ulen,
unsigned long maskp,
int  nmaskbits 
)

bitmap_parselist_user()

: 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.

Definition at line 695 of file bitmap.c.

void bitmap_release_region ( unsigned long bitmap,
int  pos,
int  order 
)

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.

Definition at line 1140 of file bitmap.c.

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.

Definition at line 811 of file bitmap.c.

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.

Definition at line 551 of file bitmap.c.

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.

Definition at line 375 of file bitmap.c.

void bitmap_set ( unsigned long map,
int  start,
int  nr 
)

Definition at line 276 of file bitmap.c.

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  )