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(addr: t->map, size: 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(map: t->map, start: offset, nbits: len); |
85 | if (offset == t->first_free) |
86 | t->first_free = find_next_zero_bit |
87 | (addr: t->map, size: t->size, |
88 | offset: 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(dst: map, nbits: size); |
124 | memset(t, 0, sizeof *t); |
125 | spin_lock_init(&t->lock); |
126 | t->map = map; |
127 | t->size = size; |
128 | } |
129 | |