1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * bitext.c: kernel little helper (of bit shuffling variety). 4 * 5 * Copyright (C) 2002 Pete Zaitcev <zaitcev@yahoo.com> 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; /* 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 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(); /* Much too late to do any good, but alas... */ 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 } 129