• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * bitext.c: kernel little helper (of bit shuffling variety).
3  *
4  * Copyright (C) 2002 Pete Zaitcev <zaitcev@yahoo.com>
5  *
6  * The algorithm to search a zero bit string is geared towards its application.
7  * We expect a couple of fixed sizes of requests, so a rotating counter, reset
8  * by align size, should provide fast enough search while maintaining low
9  * fragmentation.
10  */
11 
12 #include <linux/string.h>
13 #include <linux/bitmap.h>
14 
15 #include <asm/bitext.h>
16 
17 /**
18  * bit_map_string_get - find and set a bit string in bit map.
19  * @t: the bit map.
20  * @len: requested string length
21  * @align: requested alignment
22  *
23  * Returns offset in the map or -1 if out of space.
24  *
25  * Not safe to call from an interrupt (uses spin_lock).
26  */
bit_map_string_get(struct bit_map * t,int len,int align)27 int bit_map_string_get(struct bit_map *t, int len, int align)
28 {
29 	int offset, count;	/* siamese twins */
30 	int off_new;
31 	int align1;
32 	int i, color;
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(&t->lock);
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(&t->lock);
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(&t->lock);
93 				return offset;
94 			}
95 		}
96 		count += i + 1;
97 		if ((offset += i + 1) >= t->size)
98 			offset = 0;
99 	}
100 }
101 
bit_map_clear(struct bit_map * t,int offset,int len)102 void bit_map_clear(struct bit_map *t, int offset, int len)
103 {
104 	int i;
105 
106 	if (t->used < len)
107 		BUG();		/* Much too late to do any good, but alas... */
108 	spin_lock(&t->lock);
109 	for (i = 0; i < len; i++) {
110 		if (test_bit(offset + i, t->map) == 0)
111 			BUG();
112 		__clear_bit(offset + i, t->map);
113 	}
114 	if (offset < t->first_free)
115 		t->first_free = offset;
116 	t->used -= len;
117 	spin_unlock(&t->lock);
118 }
119 
bit_map_init(struct bit_map * t,unsigned long * map,int size)120 void bit_map_init(struct bit_map *t, unsigned long *map, int size)
121 {
122 	bitmap_zero(map, size);
123 	memset(t, 0, sizeof *t);
124 	spin_lock_init(&t->lock);
125 	t->map = map;
126 	t->size = size;
127 }
128