2 * ----------------------------------------------------------------------------
3 * "THE BEER-WARE LICENSE" (Revision 42):
4 * <phk@login.dknet.dk> wrote this file. As long as you retain this notice you
5 * can do whatever you want with this stuff. If we meet some day, and you think
6 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
7 * ----------------------------------------------------------------------------
9 * $FreeBSD: src/lib/libdisk/chunk.c,v 1.21.2.6 2002/01/07 07:53:29 dillon Exp $
10 * $DragonFly: src/lib/libdisk/Attic/chunk.c,v 1.2 2003/06/17 04:26:49 dillon Exp $
18 #include <sys/types.h>
22 #define new_chunk() memset(malloc(sizeof(struct chunk)), 0, sizeof(struct chunk))
24 /* Is c2 completely inside c1 ? */
27 Chunk_Inside(struct chunk *c1, struct chunk *c2)
29 /* if c1 ends before c2 do */
30 if (c1->end < c2->end)
32 /* if c1 starts after c2 do */
33 if (c1->offset > c2->offset)
39 Find_Mother_Chunk(struct chunk *chunks, u_long offset, u_long end, chunk_e type)
41 struct chunk *c1,*c2,ct;
47 if (Chunk_Inside(chunks, &ct))
51 for(c1 = chunks->part; c1; c1 = c1->next) {
54 if (Chunk_Inside(c1, &ct))
60 for(c1 = chunks->part; c1; c1 = c1->next) {
62 if (Chunk_Inside(c1, &ct))
64 if (c1->type != extended)
66 for(c2 = c1->part; c2; c2 = c2->next)
68 && Chunk_Inside(c2, &ct))
73 warn("Unsupported mother type in Find_Mother_Chunk");
79 Free_Chunk(struct chunk *c1)
82 if(c1->private_data && c1->private_free)
83 (*c1->private_free)(c1->private_data);
96 Clone_Chunk(struct chunk *c1)
103 if (!c2) return NULL;
105 if (c1->private_data && c1->private_clone)
106 c2->private_data = c2->private_clone(c2->private_data);
107 c2->name = strdup(c2->name);
109 c2->sname = strdup(c2->sname);
111 c2->next = Clone_Chunk(c2->next);
112 c2->part = Clone_Chunk(c2->part);
118 Insert_Chunk(struct chunk *c2, u_long offset, u_long size, const char *name,
119 chunk_e type, int subtype, u_long flags, const char *sname)
121 Insert_Chunk(struct chunk *c2, u_long offset, u_long size, const char *name,
122 chunk_e type, int subtype, u_long flags)
125 struct chunk *ct,*cs;
127 /* We will only insert into empty spaces */
128 if (c2->type != unused)
132 if (!ct) return __LINE__;
133 memset(ct, 0, sizeof *ct);
137 ct->end = offset + size - 1;
140 ct->sname = strdup(sname);
142 ct->name = strdup(name);
143 ct->subtype = subtype;
146 if (!Chunk_Inside(c2, ct)) {
151 if(type==freebsd || type==extended) {
153 if (!cs) return __LINE__;
154 memset(cs, 0, sizeof *cs);
158 cs->end = offset + size - 1;
161 cs->sname = strdup(sname);
163 cs->name = strdup("-");
167 /* Make a new chunk for any trailing unused space */
168 if (c2->end > ct->end) {
170 if (!cs) return __LINE__;
173 cs->offset = ct->end + 1;
174 cs->size = c2->end - ct->end;
177 cs->sname = strdup(c2->sname);
180 cs->name = strdup(c2->name);
182 c2->size -= c2->end - ct->end;
185 /* If no leading unused space just occupy the old chunk */
186 if (c2->offset == ct->offset) {
188 c2->sname = ct->sname;
193 c2->subtype = ct->subtype;
194 c2->flags = ct->flags;
203 /* else insert new chunk and adjust old one */
204 c2->end = ct->offset - 1;
205 c2->size -= ct->size;
213 Add_Chunk(struct disk *d, long offset, u_long size, const char *name,
214 chunk_e type, int subtype, u_long flags, const char *sname)
216 Add_Chunk(struct disk *d, long offset, u_long size, const char *name,
217 chunk_e type, int subtype, u_long flags)
220 struct chunk *c1,*c2,ct;
221 u_long end = offset + size - 1;
227 d->chunks = c1 = new_chunk();
228 if (!c1) return __LINE__;
229 memset(c1, 0, sizeof *c1);
230 c2 = c1->part = new_chunk();
231 if (!c2) return __LINE__;
232 memset(c2,0,sizeof *c2);
233 c2->disk = c1->disk = d;
234 c2->offset = c1->offset = offset;
235 c2->size = c1->size = size;
236 c2->end = c1->end = end;
238 c1->sname = strdup(sname);
239 c2->sname = strdup("-");
241 c1->name = strdup(name);
242 c2->name = strdup("-");
246 c1->subtype = subtype;
257 if(!c1 && (type == freebsd || type == fat || type == unknown))
258 c1 = Find_Mother_Chunk(d->chunks, offset, end, extended);
260 if(!c1 && (type == freebsd || type == fat || type == unknown))
261 c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
263 if(!c1 && type == extended)
264 c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
266 if(!c1 && type == part)
267 c1 = Find_Mother_Chunk(d->chunks, offset, end, freebsd);
270 for(c2 = c1->part; c2; c2 = c2->next) {
271 if (c2->type != unused)
273 if(Chunk_Inside(c2, &ct)) {
276 if (!(flags & CHUNK_ALIGN))
278 if (offset == d->chunks->offset
279 && end == d->chunks->end)
282 /* Round down to prev cylinder */
283 offset = Prev_Cyl_Aligned(d,offset);
284 /* Stay inside the parent */
285 if (offset < c2->offset)
287 /* Round up to next cylinder */
288 offset = Next_Cyl_Aligned(d, offset);
289 /* Keep one track clear in front of parent */
290 if (offset == c1->offset)
291 offset = Next_Track_Aligned(d, offset + 1);
293 /* Work on the (end+1) */
295 /* Round up to cylinder */
296 size = Next_Cyl_Aligned(d, size);
297 /* Stay inside parent */
298 if ((size-1) > c2->end)
300 /* Round down to cylinder */
301 size = Prev_Cyl_Aligned(d, size);
303 /* Convert back to size */
308 return Insert_Chunk(c2, offset, size, name,
309 type, subtype, flags, sname);
311 return Insert_Chunk(c2, offset, size, name,
312 type, subtype, flags);
320 ShowChunkFlags(struct chunk *c)
325 if (c->flags & CHUNK_BSD_COMPAT) ret[i++] = 'C';
326 if (c->flags & CHUNK_ACTIVE) ret[i++] = 'A';
327 if (c->flags & CHUNK_ALIGN) ret[i++] = '=';
328 if (c->flags & CHUNK_IS_ROOT) ret[i++] = 'R';
334 Print_Chunk(struct chunk *c1,int offset)
338 for(i = 0; i < offset - 2; i++) putchar(' ');
339 for(; i < offset; i++) putchar('-');
341 for(; i < 10; i++) putchar(' ');
343 printf("%p %8ld %8lu %8lu %-8s %-16s %-8s 0x%02x %s",
344 c1, c1->offset, c1->size, c1->end, c1->name, c1->sname,
346 printf("%p %8ld %8lu %8lu %-8s %-8s 0x%02x %s",
347 c1, c1->offset, c1->size, c1->end, c1->name,
349 chunk_n[c1->type], c1->subtype,
352 Print_Chunk(c1->part, offset + 2);
353 Print_Chunk(c1->next, offset);
357 Debug_Chunk(struct chunk *c1)
363 Delete_Chunk(struct disk *d, struct chunk *c)
365 return(Delete_Chunk2(d, c, 0));
369 Delete_Chunk2(struct disk *d, struct chunk *c, int rflags)
371 struct chunk *c1=0, *c2, *c3;
372 chunk_e type = c->type;
373 long offset = c->offset;
378 if(!c1 && (type == freebsd || type == fat || type == unknown))
379 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, extended);
381 if(!c1 && (type == freebsd || type == fat || type == unknown))
382 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, whole);
384 if(!c1 && type == extended)
385 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, whole);
387 if(!c1 && type == part)
388 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, freebsd);
391 for(c2 = c1->part; c2; c2 = c2->next) {
398 c2->sname = strdup("-");
401 c2->name = strdup("-");
402 Free_Chunk(c2->part);
410 * Collapse multiple unused elements together, and attempt
411 * to extend the previous chunk into the freed chunk.
413 * We only extend non-unused elements which are marked
414 * for newfs (we can't extend working filesystems), and
415 * only if we are called with DELCHUNK_RECOVER.
417 for(c2 = c1->part; c2; c2 = c2->next) {
418 if (c2->type != unused) {
419 if (c2->offset + c2->size != offset ||
420 (rflags & DELCHUNK_RECOVER) == 0 ||
421 (c2->flags & CHUNK_NEWFS) == 0) {
424 /* else extend into free area */
428 if (c2->next->type != unused)
431 c2->size += c3->size;
444 Collapse_Chunk(struct disk *d, struct chunk *c1)
446 struct chunk *c2, *c3;
448 if(c1->next && Collapse_Chunk(d, c1->next))
451 if(c1->type == unused && c1->next && c1->next->type == unused) {
453 c1->size += c3->size;
463 if (Collapse_Chunk(d, c1->part))
466 if (c1->type == whole)
469 if(c3->type == unused && c3->size == c1->size) {
473 if(c3->type == unused) {
475 if (!c2) barfout(1, "malloc failed");
480 c1->sname = strdup("-");
482 c1->name = strdup("-");
489 c2->offset += c1->size;
490 c2->size -= c1->size;
496 for(c2=c3;c2->next;c2 = c2->next)
498 if (c2 && c2->type == unused) {
502 c1->size -= c2->size;