1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
/* GPLv2 or OpenIB.org BSD (MIT) See COPYING file */
#define _GNU_SOURCE
#include "bitmap.h"
#include <string.h>
#include <strings.h>
#include <ccan/minmax.h>
#define BMP_WORD_INDEX(n) ((n) / BITS_PER_LONG)
#define BMP_WORD_OFFSET(n) ((n) % BITS_PER_LONG)
#define BMP_FIRST_WORD_MASK(start) (~0UL << BMP_WORD_OFFSET(start))
#define BMP_LAST_WORD_MASK(end) (BMP_WORD_OFFSET(end) == 0 ? ~0UL : \
~BMP_FIRST_WORD_MASK(end))
/*
* Finds the first set bit in the bitmap starting from
* 'start' bit until ('end'-1) bit.
*
* Returns the set bit index if found, otherwise returns 'end'.
*/
unsigned long bitmap_find_first_bit(const unsigned long *bmp,
unsigned long start, unsigned long end)
{
unsigned long curr_offset = BMP_WORD_OFFSET(start);
unsigned long curr_idx = BMP_WORD_INDEX(start);
assert(start <= end);
for (; start < end; curr_idx++) {
unsigned long bit = ffsl(bmp[curr_idx] >> curr_offset);
if (bit)
return min(end, start + bit - 1);
start += BITS_PER_LONG - curr_offset;
curr_offset = 0;
}
return end;
}
/*
* Zeroes bitmap bits in the following range: [start,end-1]
*/
void bitmap_zero_region(unsigned long *bmp, unsigned long start,
unsigned long end)
{
unsigned long start_mask;
unsigned long last_mask;
unsigned long curr_idx = BMP_WORD_INDEX(start);
unsigned long last_idx = BMP_WORD_INDEX(end - 1);
assert(start <= end);
if (start >= end)
return;
start_mask = BMP_FIRST_WORD_MASK(start);
last_mask = BMP_LAST_WORD_MASK(end);
if (curr_idx == last_idx) {
bmp[curr_idx] &= ~(start_mask & last_mask);
return;
}
bmp[curr_idx] &= ~start_mask;
for (curr_idx++; curr_idx < last_idx; curr_idx++)
bmp[curr_idx] = 0;
bmp[curr_idx] &= ~last_mask;
}
/*
* Sets bitmap bits in the following range: [start,end-1]
*/
void bitmap_fill_region(unsigned long *bmp, unsigned long start,
unsigned long end)
{
unsigned long start_mask;
unsigned long last_mask;
unsigned long curr_idx = BMP_WORD_INDEX(start);
unsigned long last_idx = BMP_WORD_INDEX(end - 1);
assert(start <= end);
if (start >= end)
return;
start_mask = BMP_FIRST_WORD_MASK(start);
last_mask = BMP_LAST_WORD_MASK(end);
if (curr_idx == last_idx) {
bmp[curr_idx] |= (start_mask & last_mask);
return;
}
bmp[curr_idx] |= start_mask;
for (curr_idx++; curr_idx < last_idx; curr_idx++)
bmp[curr_idx] = ULONG_MAX;
bmp[curr_idx] |= last_mask;
}
/*
* Checks whether the contiguous region of region_size bits starting from
* start is free.
*
* Returns true if the said region is free, otherwise returns false.
*/
static bool bitmap_is_free_region(unsigned long *bmp, unsigned long start,
unsigned long region_size)
{
unsigned long curr_idx;
unsigned long last_idx;
unsigned long last_mask;
unsigned long start_mask;
curr_idx = BMP_WORD_INDEX(start);
start_mask = BMP_FIRST_WORD_MASK(start);
last_idx = BMP_WORD_INDEX(start + region_size - 1);
last_mask = BMP_LAST_WORD_MASK(start + region_size);
if (curr_idx == last_idx)
return !(bmp[curr_idx] & start_mask & last_mask);
if (bmp[curr_idx] & start_mask)
return false;
for (curr_idx++; curr_idx < last_idx; curr_idx++) {
if (bmp[curr_idx])
return false;
}
return !(bmp[curr_idx] & last_mask);
}
/*
* Finds a contiguous region with the size of region_size
* in the bitmap that is not set.
*
* Returns first index of such region if found,
* otherwise returns nbits.
*/
unsigned long bitmap_find_free_region(unsigned long *bmp,
unsigned long nbits,
unsigned long region_size)
{
unsigned long start;
if (!region_size)
return 0;
for (start = 0; start + region_size <= nbits; start++) {
if (bitmap_test_bit(bmp, start))
continue;
if (bitmap_is_free_region(bmp, start, region_size))
return start;
}
return nbits;
}
|
