1 /*
2 * region.c --- code which manages allocations within a region.
3 *
4 * Copyright (C) 2001 Theodore Ts'o.
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Public
8 * License.
9 * %End-Header%
10 */
11
12 #include "config.h"
13 #if HAVE_UNISTD_H
14 #include <unistd.h>
15 #endif
16 #include <string.h>
17
18 #ifdef TEST_PROGRAM
19 #undef ENABLE_NLS
20 #endif
21 #include "e2fsck.h"
22
23 struct region_el {
24 region_addr_t start;
25 region_addr_t end;
26 struct region_el *next;
27 };
28
29 struct region_struct {
30 region_addr_t min;
31 region_addr_t max;
32 struct region_el *allocated;
33 struct region_el *last;
34 };
35
region_create(region_addr_t min,region_addr_t max)36 region_t region_create(region_addr_t min, region_addr_t max)
37 {
38 region_t region;
39 errcode_t retval;
40
41 retval = ext2fs_get_memzero(sizeof(struct region_struct), ®ion);
42 if (retval)
43 return NULL;
44
45 region->min = min;
46 region->max = max;
47 region->last = NULL;
48 return region;
49 }
50
region_free(region_t region)51 void region_free(region_t region)
52 {
53 struct region_el *r, *next;
54
55 for (r = region->allocated; r; r = next) {
56 next = r->next;
57 ext2fs_free_mem(&r);
58 }
59 memset(region, 0, sizeof(struct region_struct));
60 ext2fs_free_mem(®ion);
61 }
62
region_allocate(region_t region,region_addr_t start,int n)63 int region_allocate(region_t region, region_addr_t start, int n)
64 {
65 struct region_el *r, *new_region, *prev, *next;
66 region_addr_t end;
67 errcode_t retval;
68
69 end = start+n;
70 if ((start < region->min) || (end > region->max))
71 return -1;
72 if (n == 0)
73 return 1;
74
75 if (region->last && region->last->end == start &&
76 !region->last->next) {
77 region->last->end = end;
78 return 0;
79 }
80 if (region->last && start > region->last->end &&
81 !region->last->next) {
82 r = NULL;
83 prev = region->last;
84 goto append_to_list;
85 }
86
87 /*
88 * Search through the linked list. If we find that it
89 * conflicts with something that's already allocated, return
90 * 1; if we can find an existing region which we can grow, do
91 * so. Otherwise, stop when we find the appropriate place
92 * insert a new region element into the linked list.
93 */
94 for (r = region->allocated, prev=NULL; r; prev = r, r = r->next) {
95 if (((start >= r->start) && (start < r->end)) ||
96 ((end > r->start) && (end <= r->end)) ||
97 ((start <= r->start) && (end >= r->end)))
98 return 1;
99 if (end == r->start) {
100 r->start = start;
101 return 0;
102 }
103 if (start == r->end) {
104 if ((next = r->next)) {
105 if (end > next->start)
106 return 1;
107 if (end == next->start) {
108 r->end = next->end;
109 r->next = next->next;
110 ext2fs_free_mem(&next);
111 if (!r->next)
112 region->last = r;
113 return 0;
114 }
115 }
116 r->end = end;
117 return 0;
118 }
119 if (start < r->start)
120 break;
121 }
122 /*
123 * Insert a new region element structure into the linked list
124 */
125 append_to_list:
126 retval = ext2fs_get_mem(sizeof(struct region_el), &new_region);
127 if (retval)
128 return -1;
129 new_region->start = start;
130 new_region->end = start + n;
131 new_region->next = r;
132 if (!new_region->next)
133 region->last = new_region;
134 if (prev)
135 prev->next = new_region;
136 else
137 region->allocated = new_region;
138 return 0;
139 }
140
141 #ifdef TEST_PROGRAM
142 #include <stdio.h>
143
144 #define BCODE_END 0
145 #define BCODE_CREATE 1
146 #define BCODE_FREE 2
147 #define BCODE_ALLOCATE 3
148 #define BCODE_PRINT 4
149
150 int bcode_program[] = {
151 BCODE_CREATE, 1, 1001,
152 BCODE_PRINT,
153 BCODE_ALLOCATE, 10, 10,
154 BCODE_ALLOCATE, 30, 10,
155 BCODE_PRINT,
156 BCODE_ALLOCATE, 1, 15,
157 BCODE_ALLOCATE, 15, 8,
158 BCODE_ALLOCATE, 1, 20,
159 BCODE_ALLOCATE, 1, 8,
160 BCODE_PRINT,
161 BCODE_ALLOCATE, 40, 10,
162 BCODE_PRINT,
163 BCODE_ALLOCATE, 22, 5,
164 BCODE_PRINT,
165 BCODE_ALLOCATE, 27, 3,
166 BCODE_PRINT,
167 BCODE_ALLOCATE, 20, 2,
168 BCODE_PRINT,
169 BCODE_ALLOCATE, 49, 1,
170 BCODE_ALLOCATE, 50, 5,
171 BCODE_ALLOCATE, 9, 2,
172 BCODE_ALLOCATE, 9, 1,
173 BCODE_PRINT,
174 BCODE_FREE,
175 BCODE_END
176 };
177
region_print(region_t region,FILE * f)178 void region_print(region_t region, FILE *f)
179 {
180 struct region_el *r;
181 int i = 0;
182
183 fprintf(f, "Printing region (min=%llu. max=%llu)\n\t",
184 (unsigned long long) region->min,
185 (unsigned long long) region->max);
186 for (r = region->allocated; r; r = r->next) {
187 fprintf(f, "(%llu, %llu) ",
188 (unsigned long long) r->start,
189 (unsigned long long) r->end);
190 if (++i >= 8)
191 fprintf(f, "\n\t");
192 }
193 fprintf(f, "\n");
194 }
195
main(int argc,char ** argv)196 int main(int argc, char **argv)
197 {
198 region_t r = NULL;
199 int pc = 0, ret;
200 region_addr_t start, end;
201
202
203 while (1) {
204 switch (bcode_program[pc++]) {
205 case BCODE_END:
206 exit(0);
207 case BCODE_CREATE:
208 start = bcode_program[pc++];
209 end = bcode_program[pc++];
210 printf("Creating region with args(%llu, %llu)\n",
211 (unsigned long long) start,
212 (unsigned long long) end);
213 r = region_create(start, end);
214 if (!r) {
215 fprintf(stderr, "Couldn't create region.\n");
216 exit(1);
217 }
218 break;
219 case BCODE_ALLOCATE:
220 start = bcode_program[pc++];
221 end = bcode_program[pc++];
222 ret = region_allocate(r, start, end);
223 printf("Region_allocate(%llu, %llu) returns %d\n",
224 (unsigned long long) start,
225 (unsigned long long) end, ret);
226 break;
227 case BCODE_PRINT:
228 region_print(r, stdout);
229 break;
230 }
231 }
232 if (r)
233 region_free(r);
234 }
235
236 #endif /* TEST_PROGRAM */
237