sbin/gpt/map.c

   1 /*-
   2  * Copyright (c) 2002 Marcel Moolenaar
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  *
  26  * $FreeBSD: src/sbin/gpt/map.c,v 1.6 2005/08/31 01:47:19 marcel Exp $
  27  * $DragonFly: src/sbin/gpt/map.c,v 1.2 2007/06/17 08:34:59 dillon Exp $
  28  */
  29
  30 #include <sys/types.h>
  31 #include <err.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34
  35 #include "map.h"
  36
  37 #define ROUNDTO 2048    // must be a power of two
  38 #define ROUNDDOWN(x) ((x-1) & ~(ROUNDTO-1))
  39 #define ROUNDUP(x) (ROUNDDOWN(x) + ROUNDTO)
  40
  41 int lbawidth;
  42
  43 static map_t *mediamap;
  44
  45 static map_t *
  46 mkmap(off_t start, off_t size, int type)
  47 {
  48         map_t *m;
  49
  50         m = malloc(sizeof(*m));
  51         if (m == NULL)
  52                 return (NULL);
  53         m->map_start = start;
  54         m->map_size = size;
  55         m->map_next = m->map_prev = NULL;
  56         m->map_type = type;
  57         m->map_index = NOENTRY;
  58         m->map_data = NULL;
  59         return (m);
  60 }
  61
  62 map_t *
  63 map_add(off_t start, off_t size, int type, void *data)
  64 {
  65         map_t *m, *n, *p;
  66
  67         n = mediamap;
  68         while (n != NULL && n->map_start + n->map_size <= start)
  69                 n = n->map_next;
  70         if (n == NULL)
  71                 return (NULL);
  72
  73         if (n->map_start + n->map_size < start + size) {
  74                 warnx("error: bogus map");
  75                 return (0);
  76         }
  77
  78         if (n->map_start == start && n->map_size == size) {
  79                 if (n->map_type != MAP_TYPE_UNUSED) {
  80                         if (n->map_type != MAP_TYPE_MBR_PART ||
  81                             type != MAP_TYPE_GPT_PART) {
  82                                 warnx("warning: partition(%llu,%llu) mirrored",
  83                                     (long long)start, (long long)size);
  84                         }
  85                 }
  86                 n->map_type = type;
  87                 n->map_data = data;
  88                 return (n);
  89         }
  90
  91         if (n->map_type != MAP_TYPE_UNUSED) {
  92                 if (n->map_type != MAP_TYPE_MBR_PART ||
  93                     type != MAP_TYPE_GPT_PART) {
  94                         warnx("error: bogus map");
  95                         return (0);
  96                 }
  97                 n->map_type = MAP_TYPE_UNUSED;
  98         }
  99
 100         m = mkmap(start, size, type);
 101         if (m == NULL)
 102                 return (NULL);
 103
 104         m->map_data = data;
 105
 106         if (start == n->map_start) {
 107                 m->map_prev = n->map_prev;
 108                 m->map_next = n;
 109                 if (m->map_prev != NULL)
 110                         m->map_prev->map_next = m;
 111                 else
 112                         mediamap = m;
 113                 n->map_prev = m;
 114                 n->map_start += size;
 115                 n->map_size -= size;
 116         } else if (start + size == n->map_start + n->map_size) {
 117                 p = n;
 118                 m->map_next = p->map_next;
 119                 m->map_prev = p;
 120                 if (m->map_next != NULL)
 121                         m->map_next->map_prev = m;
 122                 p->map_next = m;
 123                 p->map_size -= size;
 124         } else {
 125                 p = mkmap(n->map_start, start - n->map_start, n->map_type);
 126                 n->map_start += p->map_size + m->map_size;
 127                 n->map_size -= (p->map_size + m->map_size);
 128                 p->map_prev = n->map_prev;
 129                 m->map_prev = p;
 130                 n->map_prev = m;
 131                 m->map_next = n;
 132                 p->map_next = m;
 133                 if (p->map_prev != NULL)
 134                         p->map_prev->map_next = p;
 135                 else
 136                         mediamap = p;
 137         }
 138
 139         return (m);
 140 }
 141
 142 map_t *
 143 map_alloc(off_t start, off_t size)
 144 {
 145         off_t delta;
 146         map_t *m;
 147
 148         if (start == 0 && size != 0)
 149                 size = ROUNDUP(size);
 150         for (m = mediamap; m != NULL; m = m->map_next) {
 151                 if (m->map_type != MAP_TYPE_UNUSED || m->map_start < 2)
 152                         continue;
 153                 if (start != 0 && m->map_start > start)
 154                         return (NULL);
 155                 delta = (start != 0) ? start - m->map_start : ROUNDUP(m->map_start) - m->map_start;
 156                 if (size == 0 || m->map_size - delta >= size) {
 157                         if (m->map_size - delta <= 0)
 158                                 continue;
 159                         if (size == 0) {
 160                                 size = m->map_size - delta;
 161                                 if (start == 0)
 162                                         size = ROUNDDOWN(size);
 163                         }
 164                         return (map_add(m->map_start + delta, size,
 165                                     MAP_TYPE_GPT_PART, NULL));
 166                 }
 167         }
 168
 169         return (NULL);
 170 }
 171
 172 map_t *
 173 map_find(int type)
 174 {
 175         map_t *m;
 176
 177         m = mediamap;
 178         while (m != NULL && m->map_type != type)
 179                 m = m->map_next;
 180         return (m);
 181 }
 182
 183 map_t *
 184 map_first(void)
 185 {
 186         return mediamap;
 187 }
 188
 189 map_t *
 190 map_last(void)
 191 {
 192         map_t *m;
 193
 194         m = mediamap;
 195         while (m != NULL && m->map_next != NULL)
 196                 m = m->map_next;
 197         return (m);
 198 }
 199
 200 off_t
 201 map_free(off_t start, off_t size)
 202 {
 203         map_t *m;
 204
 205         m = mediamap;
 206
 207         while (m != NULL && m->map_start + m->map_size <= start)
 208                 m = m->map_next;
 209         if (m == NULL || m->map_type != MAP_TYPE_UNUSED)
 210                 return (0LL);
 211         if (size)
 212                 return ((m->map_start + m->map_size >= start + size) ? 1 : 0);
 213         return (m->map_size - (start - m->map_start));
 214 }
 215
 216 void
 217 map_init(off_t size)
 218 {
 219         char buf[32];
 220
 221         mediamap = mkmap(0LL, size, MAP_TYPE_UNUSED);
 222         lbawidth = sprintf(buf, "%llu", (long long)size);
 223         if (lbawidth < 5)
 224                 lbawidth = 5;
 225 }