1 /* 2 * bitext.c: kernel little helper (of bit shuffling variety). 3 * 4 * Copyright (C) 2002 Pete Zaitcev <zaitcev@yahoo.com> 5 * 6 * The algorithm to search a zero bit string is geared towards its application. 7 * We expect a couple of fixed sizes of requests, so a rotating counter, reset 8 * by align size, should provide fast enough search while maintaining low 9 * fragmentation. 10 */ 11 12 #include <linux/smp_lock.h> 13 #include <linux/string.h> 14 #include <linux/bitops.h> 15 16 #include <asm/bitext.h> 17 18 /** 19 * bit_map_string_get - find and set a bit string in bit map. 20 * @t: the bit map. 21 * @len: requested string length 22 * @align: requested alignment 23 * 24 * Returns offset in the map or -1 if out of space. 25 * 26 * Not safe to call from an interrupt (uses spin_lock). 27 */ 28 int bit_map_string_get(struct bit_map *t, int len, int align) 29 { 30 int offset, count; /* siamese twins */ 31 int off_new; 32 int align1; 33 int i, color; 34 35 if (t->num_colors) { 36 /* align is overloaded to be the page color */ 37 color = align; 38 align = t->num_colors; 39 } else { 40 color = 0; 41 if (align == 0) 42 align = 1; 43 } 44 align1 = align - 1; 45 if ((align & align1) != 0) 46 BUG(); 47 if (align < 0 || align >= t->size) 48 BUG(); 49 if (len <= 0 || len > t->size) 50 BUG(); 51 color &= align1; 52 53 spin_lock(&t->lock); 54 if (len < t->last_size) 55 offset = t->first_free; 56 else 57 offset = t->last_off & ~align1; 58 count = 0; 59 for (;;) { 60 off_new = find_next_zero_bit(t->map, t->size, offset); 61 off_new = ((off_new + align1) & ~align1) + color; 62 count += off_new - offset; 63 offset = off_new; 64 if (offset >= t->size) 65 offset = 0; 66 if (count + len > t->size) { 67 spin_unlock(&t->lock); 68 /* P3 */ printk(KERN_ERR 69 "bitmap out: size %d used %d off %d len %d align %d count %d\n", 70 t->size, t->used, offset, len, align, count); 71 return -1; 72 } 73 74 if (offset + len > t->size) { 75 count += t->size - offset; 76 offset = 0; 77 continue; 78 } 79 80 i = 0; 81 while (test_bit(offset + i, t->map) == 0) { 82 i++; 83 if (i == len) { 84 for (i = 0; i < len; i++) 85 __set_bit(offset + i, t->map); 86 if (offset == t->first_free) 87 t->first_free = find_next_zero_bit 88 (t->map, t->size, 89 t->first_free + len); 90 if ((t->last_off = offset + len) >= t->size) 91 t->last_off = 0; 92 t->used += len; 93 t->last_size = len; 94 spin_unlock(&t->lock); 95 return offset; 96 } 97 } 98 count += i + 1; 99 if ((offset += i + 1) >= t->size) 100 offset = 0; 101 } 102 } 103 104 void bit_map_clear(struct bit_map *t, int offset, int len) 105 { 106 int i; 107 108 if (t->used < len) 109 BUG(); /* Much too late to do any good, but alas... */ 110 spin_lock(&t->lock); 111 for (i = 0; i < len; i++) { 112 if (test_bit(offset + i, t->map) == 0) 113 BUG(); 114 __clear_bit(offset + i, t->map); 115 } 116 if (offset < t->first_free) 117 t->first_free = offset; 118 t->used -= len; 119 spin_unlock(&t->lock); 120 } 121 122 void bit_map_init(struct bit_map *t, unsigned long *map, int size) 123 { 124 125 if ((size & 07) != 0) 126 BUG(); 127 memset(map, 0, size>>3); 128 129 memset(t, 0, sizeof *t); 130 spin_lock_init(&t->lock); 131 t->map = map; 132 t->size = size; 133 } 134