Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
1da177e4 LT |
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 | ||
f037360f | 13 | #include <linux/string.h> |
e637804c | 14 | #include <linux/bitmap.h> |
1da177e4 LT |
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) { | |
e637804c | 84 | bitmap_set(t->map, offset, len); |
1da177e4 LT |
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 | { | |
54df2db3 | 123 | bitmap_zero(map, size); |
1da177e4 LT |
124 | memset(t, 0, sizeof *t); |
125 | spin_lock_init(&t->lock); | |
126 | t->map = map; | |
127 | t->size = size; | |
128 | } |