| 1 | |
| 2 | |
| 3 | * bitext.c: kernel little helper (of bit shuffling variety).
|
| 4 | *
|
| 5 | * Copyright (C) 2002 Pete Zaitcev <[email protected]>
|
| 6 | *
|
| 7 | * The algorithm to search a zero bit string is geared towards its application.
|
| 8 | * We expect a couple of fixed sizes of requests, so a rotating counter, reset
|
| 9 | * by align size, should provide fast enough search while maintaining low
|
| 10 | * fragmentation.
|
| 11 |
|
| 12 |
|
| 13 | #include <linux/string.h>
|
| 14 | #include <linux/bitmap.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;
|
| 31 | int off_new;
|
| 32 | int align1;
|
| 33 | int i, color;
|
| 34 |
|
| 35 | if (t->num_colors) {
|
| 36 |
|
| 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 | 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 | bitmap_set(t->map, offset, len);
|
| 85 | if (offset == t->first_free)
|
| 86 | t->first_free = find_next_zero_bit
|
| 87 | (t->map, t->size,
|
| 88 | t->first_free + len);
|
| 89 | if ((t->last_off = offset + len) >= t->size)
|
| 90 | t->last_off = 0;
|
| 91 | t->used += len;
|
| 92 | t->last_size = len;
|
| 93 | spin_unlock(&t->lock);
|
| 94 | return offset;
|
| 95 | }
|
| 96 | }
|
| 97 | count += i + 1;
|
| 98 | if ((offset += i + 1) >= t->size)
|
| 99 | offset = 0;
|
| 100 | }
|
| 101 | }
|
| 102 |
|
| 103 | void bit_map_clear(struct bit_map *t, int offset, int len)
|
| 104 | {
|
| 105 | int i;
|
| 106 |
|
| 107 | if (t->used < len)
|
| 108 | BUG();
|
| 109 | spin_lock(&t->lock);
|
| 110 | for (i = 0; i < len; i++) {
|
| 111 | if (test_bit(offset + i, t->map) == 0)
|
| 112 | BUG();
|
| 113 | __clear_bit(offset + i, t->map);
|
| 114 | }
|
| 115 | if (offset < t->first_free)
|
| 116 | t->first_free = offset;
|
| 117 | t->used -= len;
|
| 118 | spin_unlock(&t->lock);
|
| 119 | }
|
| 120 |
|
| 121 | void bit_map_init(struct bit_map *t, unsigned long *map, int size)
|
| 122 | {
|
| 123 | bitmap_zero(map, size);
|
| 124 | memset(t, 0, sizeof *t);
|
| 125 | spin_lock_init(&t->lock);
|
| 126 | t->map = map;
|
| 127 | t->size = size;
|
| 128 | }
|