Makefile: Use $(MAKE) instead of plain 'make'.
[pintos-anon] / src / lib / kernel / bitmap.c
1 #include "bitmap.h"
2 #include <debug.h>
3 #include <limits.h>
4 #include <round.h>
5 #include <stdio.h>
6 #include "threads/malloc.h"
7 #ifdef FILESYS
8 #include "filesys/file.h"
9 #endif
10 \f
11 /* Element type.
12
13    This must be an unsigned integer type at least as wide as int.
14
15    Each bit represents one bit in the bitmap.
16    If bit 0 in an element represents bit K in the bitmap,
17    then bit 1 in the element represents bit K+1 in the bitmap,
18    and so on. */
19 typedef unsigned long elem_type;
20
21 /* Number of bits in an element. */
22 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
23
24 /* From the outside, a bitmap is an array of bits.  From the
25    inside, it's an array of elem_type (defined above) that
26    simulates an array of bits. */
27 struct bitmap
28   {
29     size_t bit_cnt;     /* Number of bits. */
30     elem_type *bits;    /* Elements that represent bits. */
31   };
32
33 /* Returns the index of the element that contains the bit
34    numbered BIT_IDX. */
35 static inline size_t
36 elem_idx (size_t bit_idx) 
37 {
38   return bit_idx / ELEM_BITS;
39 }
40
41 /* Returns an elem_type where only the bit corresponding to
42    BIT_IDX is turned on. */
43 static inline elem_type
44 bit_mask (size_t bit_idx) 
45 {
46   return (elem_type) 1 << (bit_idx % ELEM_BITS);
47 }
48
49 /* Returns the number of elements required for BIT_CNT bits. */
50 static inline size_t
51 elem_cnt (size_t bit_cnt)
52 {
53   return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
54 }
55
56 /* Returns the number of bytes required for BIT_CNT bits. */
57 static inline size_t
58 byte_cnt (size_t bit_cnt)
59 {
60   return sizeof (elem_type) * elem_cnt (bit_cnt);
61 }
62
63 /* Returns a bit mask in which the bits actually used in the last
64    element of B's bits are set to 1 and the rest are set to 0. */
65 static inline elem_type
66 last_mask (const struct bitmap *b) 
67 {
68   int last_bits = b->bit_cnt % ELEM_BITS;
69   return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
70 }
71 \f
72 /* Creation and destruction. */
73
74 /* Initializes B to be a bitmap of BIT_CNT bits
75    and sets all of its bits to false.
76    Returns true if success, false if memory allocation
77    failed. */
78 struct bitmap *
79 bitmap_create (size_t bit_cnt) 
80 {
81   struct bitmap *b = malloc (sizeof *b);
82   if (b != NULL)
83     {
84       b->bit_cnt = bit_cnt;
85       b->bits = malloc (byte_cnt (bit_cnt));
86       if (b->bits != NULL || bit_cnt == 0)
87         {
88           bitmap_set_all (b, false);
89           return b;
90         }
91       free (b);
92     }
93   return NULL;
94 }
95
96 /* Creates and returns a bitmap with BIT_CNT bits in the
97    BLOCK_SIZE bytes of storage preallocated at BLOCK.
98    BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
99 struct bitmap *
100 bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
101 {
102   struct bitmap *b = block;
103   
104   ASSERT (block_size >= bitmap_buf_size (bit_cnt));
105
106   b->bit_cnt = bit_cnt;
107   b->bits = (elem_type *) (b + 1);
108   bitmap_set_all (b, false);
109   return b;
110 }
111
112 /* Returns the number of bytes required to accomodate a bitmap
113    with BIT_CNT bits (for use with bitmap_create_in_buf()). */
114 size_t
115 bitmap_buf_size (size_t bit_cnt) 
116 {
117   return sizeof (struct bitmap) + byte_cnt (bit_cnt);
118 }
119
120 /* Destroys bitmap B, freeing its storage.
121    Not for use on bitmaps created by
122    bitmap_create_preallocated(). */
123 void
124 bitmap_destroy (struct bitmap *b) 
125 {
126   if (b != NULL) 
127     {
128       free (b->bits);
129       free (b);
130     }
131 }
132 \f
133 /* Bitmap size. */
134
135 /* Returns the number of bits in B. */
136 size_t
137 bitmap_size (const struct bitmap *b)
138 {
139   return b->bit_cnt;
140 }
141 \f
142 /* Setting and testing single bits. */
143
144 /* Atomically sets the bit numbered IDX in B to VALUE. */
145 void
146 bitmap_set (struct bitmap *b, size_t idx, bool value) 
147 {
148   ASSERT (b != NULL);
149   ASSERT (idx < b->bit_cnt);
150   if (value)
151     bitmap_mark (b, idx);
152   else
153     bitmap_reset (b, idx);
154 }
155
156 /* Atomically sets the bit numbered BIT_IDX in B to true. */
157 void
158 bitmap_mark (struct bitmap *b, size_t bit_idx) 
159 {
160   size_t idx = elem_idx (bit_idx);
161   elem_type mask = bit_mask (bit_idx);
162
163   /* This is equivalent to `b->bits[idx] |= mask' except that it
164      is guaranteed to be atomic on a uniprocessor machine.  See
165      the description of the OR instruction in [IA32-v2b]. */
166   asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
167 }
168
169 /* Atomically sets the bit numbered BIT_IDX in B to false. */
170 void
171 bitmap_reset (struct bitmap *b, size_t bit_idx) 
172 {
173   size_t idx = elem_idx (bit_idx);
174   elem_type mask = bit_mask (bit_idx);
175
176   /* This is equivalent to `b->bits[idx] &= ~mask' except that it
177      is guaranteed to be atomic on a uniprocessor machine.  See
178      the description of the AND instruction in [IA32-v2a]. */
179   asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
180 }
181
182 /* Atomically toggles the bit numbered IDX in B;
183    that is, if it is true, makes it false,
184    and if it is false, makes it true. */
185 void
186 bitmap_flip (struct bitmap *b, size_t bit_idx) 
187 {
188   size_t idx = elem_idx (bit_idx);
189   elem_type mask = bit_mask (bit_idx);
190
191   /* This is equivalent to `b->bits[idx] ^= mask' except that it
192      is guaranteed to be atomic on a uniprocessor machine.  See
193      the description of the XOR instruction in [IA32-v2b]. */
194   asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
195 }
196
197 /* Returns the value of the bit numbered IDX in B. */
198 bool
199 bitmap_test (const struct bitmap *b, size_t idx) 
200 {
201   ASSERT (b != NULL);
202   ASSERT (idx < b->bit_cnt);
203   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
204 }
205 \f
206 /* Setting and testing multiple bits. */
207
208 /* Sets all bits in B to VALUE. */
209 void
210 bitmap_set_all (struct bitmap *b, bool value) 
211 {
212   ASSERT (b != NULL);
213
214   bitmap_set_multiple (b, 0, bitmap_size (b), value);
215 }
216
217 /* Sets the CNT bits starting at START in B to VALUE. */
218 void
219 bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value) 
220 {
221   size_t i;
222   
223   ASSERT (b != NULL);
224   ASSERT (start <= b->bit_cnt);
225   ASSERT (start + cnt <= b->bit_cnt);
226
227   for (i = 0; i < cnt; i++)
228     bitmap_set (b, start + i, value);
229 }
230
231 /* Returns the number of bits in B between START and START + CNT,
232    exclusive, that are set to VALUE. */
233 size_t
234 bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value) 
235 {
236   size_t i, value_cnt;
237
238   ASSERT (b != NULL);
239   ASSERT (start <= b->bit_cnt);
240   ASSERT (start + cnt <= b->bit_cnt);
241
242   value_cnt = 0;
243   for (i = 0; i < cnt; i++)
244     if (bitmap_test (b, start + i) == value)
245       value_cnt++;
246   return value_cnt;
247 }
248
249 /* Returns true if any bits in B between START and START + CNT,
250    exclusive, are set to VALUE, and false otherwise. */
251 bool
252 bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value) 
253 {
254   size_t i;
255   
256   ASSERT (b != NULL);
257   ASSERT (start <= b->bit_cnt);
258   ASSERT (start + cnt <= b->bit_cnt);
259
260   for (i = 0; i < cnt; i++)
261     if (bitmap_test (b, start + i) == value)
262       return true;
263   return false;
264 }
265
266 /* Returns true if any bits in B between START and START + CNT,
267    exclusive, are set to true, and false otherwise.*/
268 bool
269 bitmap_any (const struct bitmap *b, size_t start, size_t cnt) 
270 {
271   return bitmap_contains (b, start, cnt, true);
272 }
273
274 /* Returns true if no bits in B between START and START + CNT,
275    exclusive, are set to true, and false otherwise.*/
276 bool
277 bitmap_none (const struct bitmap *b, size_t start, size_t cnt) 
278 {
279   return !bitmap_contains (b, start, cnt, true);
280 }
281
282 /* Returns true if every bit in B between START and START + CNT,
283    exclusive, is set to true, and false otherwise. */
284 bool
285 bitmap_all (const struct bitmap *b, size_t start, size_t cnt) 
286 {
287   return !bitmap_contains (b, start, cnt, false);
288 }
289 \f
290 /* Finding set or unset bits. */
291
292 /* Finds and returns the starting index of the first group of CNT
293    consecutive bits in B at or after START that are all set to
294    VALUE.
295    If there is no such group, returns BITMAP_ERROR. */
296 size_t
297 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value) 
298 {
299   ASSERT (b != NULL);
300   ASSERT (start <= b->bit_cnt);
301
302   if (cnt <= b->bit_cnt) 
303     {
304       size_t last = b->bit_cnt - cnt;
305       size_t i;
306       for (i = start; i <= last; i++)
307         if (!bitmap_contains (b, i, cnt, !value))
308           return i; 
309     }
310   return BITMAP_ERROR;
311 }
312
313 /* Finds the first group of CNT consecutive bits in B at or after
314    START that are all set to VALUE, flips them all to !VALUE,
315    and returns the index of the first bit in the group.
316    If there is no such group, returns BITMAP_ERROR.
317    If CNT is zero, returns 0.
318    Bits are set atomically, but testing bits is not atomic with
319    setting them. */
320 size_t
321 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
322 {
323   size_t idx = bitmap_scan (b, start, cnt, value);
324   if (idx != BITMAP_ERROR) 
325     bitmap_set_multiple (b, idx, cnt, !value);
326   return idx;
327 }
328 \f
329 /* File input and output. */
330
331 #ifdef FILESYS
332 /* Returns the number of bytes needed to store B in a file. */
333 size_t
334 bitmap_file_size (const struct bitmap *b) 
335 {
336   return byte_cnt (b->bit_cnt);
337 }
338
339 /* Reads B from FILE.  Returns true if successful, false
340    otherwise. */
341 bool
342 bitmap_read (struct bitmap *b, struct file *file) 
343 {
344   bool success = true;
345   if (b->bit_cnt > 0) 
346     {
347       off_t size = byte_cnt (b->bit_cnt);
348       success = file_read_at (file, b->bits, size, 0) == size;
349       b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
350     }
351   return success;
352 }
353
354 /* Writes B to FILE.  Return true if successful, false
355    otherwise. */
356 bool
357 bitmap_write (const struct bitmap *b, struct file *file)
358 {
359   off_t size = byte_cnt (b->bit_cnt);
360   return file_write_at (file, b->bits, size, 0) == size;
361 }
362 #endif /* FILESYS */
363 \f
364 /* Debugging. */
365
366 /* Dumps the contents of B to the console as hexadecimal. */
367 void
368 bitmap_dump (const struct bitmap *b) 
369 {
370   hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
371 }
372