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 int bit_map_string_get(struct bit_map *t, int len, int align) 27 { 28 int offset, count; /* siamese twins */ 29 int off_new; 30 int align1; 31 int i, color; 32 unsigned long flags; 33 34 if (t->num_colors) { 35 /* align is overloaded to be the page color */ 36 color = align; 37 align = t->num_colors; 38 } else { 39 color = 0; 40 if (align == 0) 41 align = 1; 42 } 43 align1 = align - 1; 44 if ((align & align1) != 0) 45 BUG(); 46 if (align < 0 || align >= t->size) 47 BUG(); 48 if (len <= 0 || len > t->size) 49 BUG(); 50 color &= align1; 51 52 spin_lock_irqsave(&t->lock, flags); 53 if (len < t->last_size) 54 offset = t->first_free; 55 else 56 offset = t->last_off & ~align1; 57 count = 0; 58 for (;;) { 59 off_new = find_next_zero_bit(t->map, t->size, offset); 60 off_new = ((off_new + align1) & ~align1) + color; 61 count += off_new - offset; 62 offset = off_new; 63 if (offset >= t->size) 64 offset = 0; 65 if (count + len > t->size) { 66 spin_unlock_irqrestore(&t->lock, flags); 67 /* P3 */ printk(KERN_ERR 68 "bitmap out: size %d used %d off %d len %d align %d count %d\n", 69 t->size, t->used, offset, len, align, count); 70 return -1; 71 } 72 73 if (offset + len > t->size) { 74 count += t->size - offset; 75 offset = 0; 76 continue; 77 } 78 79 i = 0; 80 while (test_bit(offset + i, t->map) == 0) { 81 i++; 82 if (i == len) { 83 bitmap_set(t->map, offset, len); 84 if (offset == t->first_free) 85 t->first_free = find_next_zero_bit 86 (t->map, t->size, 87 t->first_free + len); 88 if ((t->last_off = offset + len) >= t->size) 89 t->last_off = 0; 90 t->used += len; 91 t->last_size = len; 92 spin_unlock_irqrestore(&t->lock, flags); 93 return offset; 94 } 95 } 96 count += i + 1; 97 if ((offset += i + 1) >= t->size) 98 offset = 0; 99 } 100 } 101 102 void bit_map_clear(struct bit_map *t, int offset, int len) 103 { 104 int i; 105 unsigned long flags; 106 107 if (t->used < len) 108 BUG(); /* Much too late to do any good, but alas... */ 109 spin_lock_irqsave(&t->lock, flags); 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_irqrestore(&t->lock, flags); 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