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