livefiles_hfs_plugin/lf_hfs_rangelist.c

   1 /*  Copyright © 2017-2018 Apple Inc. All rights reserved.
   2  *
   3  *  lf_hfs_rangelist.c
   4  *  livefiles_hfs
   5  *
   6  *  Created by Yakov Ben Zaken on 19/03/2018.
   7  */
   8
   9 #include "lf_hfs_rangelist.h"
  10 #include "lf_hfs_vfsutils.h"
  11
  12 static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range);
  13 static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range);
  14 static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range);
  15
  16 /*
  17  * Walk the list of ranges for an entry to
  18  * find an overlapping range (if any).
  19  *
  20  * NOTE: this returns only the FIRST overlapping range.
  21  *         There may be more than one.
  22  */
  23 static enum rl_overlaptype
  24 rl_scan_from(struct rl_head *rangelist __unused,
  25              off_t start,
  26              off_t end,
  27              struct rl_entry **overlap,
  28              struct rl_entry *range)
  29 {
  30
  31     while (range)
  32     {
  33         enum rl_overlaptype ot = rl_overlap(range, start, end);
  34
  35         if (ot != RL_NOOVERLAP || range->rl_start > end)
  36         {
  37             *overlap = range;
  38             return ot;
  39         }
  40
  41         range = TAILQ_NEXT(range, rl_link);
  42     }
  43
  44     *overlap = NULL;
  45     return RL_NOOVERLAP;
  46 }
  47
  48 void
  49 rl_init(struct rl_head *rangelist)
  50 {
  51     TAILQ_INIT(rangelist);
  52 }
  53
  54 enum rl_overlaptype
  55 rl_overlap(const struct rl_entry *range, off_t start, off_t end)
  56 {
  57     /*
  58      * OK, check for overlap
  59      *
  60      * Six cases:
  61      *    0) no overlap (RL_NOOVERLAP)
  62      *    1) overlap == range (RL_MATCHINGOVERLAP)
  63      *    2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
  64      *    3) range contains overlap (RL_OVERLAPISCONTAINED)
  65      *    4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
  66      *    5) overlap ends after range (RL_OVERLAPENDSAFTER)
  67      */
  68     if (start > range->rl_end || range->rl_start > end)
  69     {
  70         /* Case 0 (RL_NOOVERLAP) */
  71         return RL_NOOVERLAP;
  72     }
  73
  74     if (range->rl_start == start && range->rl_end == end)
  75     {
  76         /* Case 1 (RL_MATCHINGOVERLAP) */
  77         return RL_MATCHINGOVERLAP;
  78     }
  79
  80     if (range->rl_start <= start && range->rl_end >= end)
  81     {
  82         /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
  83         return RL_OVERLAPCONTAINSRANGE;
  84     }
  85
  86     if (start <= range->rl_start && end >= range->rl_end)
  87     {
  88         /* Case 3 (RL_OVERLAPISCONTAINED) */
  89         return RL_OVERLAPISCONTAINED;
  90     }
  91
  92     if (range->rl_start < start && range->rl_end < end)
  93     {
  94         /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
  95         return RL_OVERLAPSTARTSBEFORE;
  96     }
  97
  98     /* Case 5 (RL_OVERLAPENDSAFTER) */
  99     // range->rl_start > start && range->rl_end > end
 100     return RL_OVERLAPENDSAFTER;
 101 }
 102
 103 /*
 104  * Remove a range from a range list.
 105  *
 106  * Generally, find the range (or an overlap to that range)
 107  * and remove it (or shrink it), then wakeup anyone we can.
 108  */
 109 void
 110 rl_remove(off_t start, off_t end, struct rl_head *rangelist)
 111 {
 112     struct rl_entry *range, *next_range, *overlap, *splitrange;
 113     int ovcase;
 114
 115     if (TAILQ_EMPTY(rangelist))
 116     {
 117         return;
 118     };
 119
 120     range = TAILQ_FIRST(rangelist);
 121     while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range)))
 122     {
 123         switch (ovcase)
 124         {
 125
 126             case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 127                 TAILQ_REMOVE(rangelist, overlap, rl_link);
 128                 hfs_free(overlap);
 129                 break;
 130
 131             case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
 132                 if (overlap->rl_start == start) {
 133                     overlap->rl_start = end + 1;
 134                     break;
 135                 };
 136
 137                 if (overlap->rl_end == end) {
 138                     overlap->rl_end = start - 1;
 139                     break;
 140                 };
 141
 142                 /*
 143                  * Make a new range consisting of the last part of the encompassing range
 144                  */
 145                 splitrange = hfs_malloc(sizeof(struct rl_entry));
 146                 splitrange->rl_start = end + 1;
 147                 splitrange->rl_end = overlap->rl_end;
 148                 overlap->rl_end = start - 1;
 149
 150                 /*
 151                  * Now link the new entry into the range list after the range from which it was split:
 152                  */
 153                 TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
 154                 break;
 155
 156             case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 157                 /* Check before discarding overlap entry */
 158                 next_range = TAILQ_NEXT(overlap, rl_link);
 159                 TAILQ_REMOVE(rangelist, overlap, rl_link);
 160                 hfs_free(overlap);
 161                 if (next_range)
 162                 {
 163                     range = next_range;
 164                     continue;
 165                 };
 166                 break;
 167
 168             case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 169                 overlap->rl_end = start - 1;
 170                 range = TAILQ_NEXT(overlap, rl_link);
 171                 if (range) {
 172                     continue;
 173                 }
 174                 break;
 175
 176             case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 177                 overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
 178                 break;
 179         }
 180         break;
 181     }
 182 }
 183
 184 off_t rl_len(const struct rl_entry *range)
 185 {
 186     return range->rl_end - range->rl_start + 1;
 187 }
 188
 189 void rl_remove_all(struct rl_head *rangelist)
 190 {
 191     struct rl_entry *r, *nextr;
 192     TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr){
 193         hfs_free(r);
 194     }
 195     TAILQ_INIT(rangelist);
 196 }
 197
 198 /*
 199  * Add a range to the list
 200  */
 201 void
 202 rl_add(off_t start, off_t end, struct rl_head *rangelist)
 203 {
 204     struct rl_entry *range;
 205     struct rl_entry *overlap;
 206     enum rl_overlaptype ovcase;
 207
 208 #ifdef RL_DIAGNOSTIC
 209     if (end < start)
 210     {
 211         LFHFS_LOG(LEVEL_ERROR, "rl_add: end < start?!");
 212         hfs_assert(0);
 213     }
 214 #endif
 215
 216     ovcase = rl_scan(rangelist, start, end, &overlap);
 217
 218     /*
 219      * Six cases:
 220      *    0) no overlap
 221      *    1) overlap == range
 222      *    2) overlap contains range
 223      *    3) range contains overlap
 224      *    4) overlap starts before range
 225      *    5) overlap ends after range
 226      */
 227     switch (ovcase) {
 228         case RL_NOOVERLAP: /* 0: no overlap */
 229             /*
 230              * overlap points to the entry we should insert before, or
 231              * if NULL, we should insert at the end.
 232              */
 233             range = hfs_mallocz(sizeof(*range));
 234             range->rl_start = start;
 235             range->rl_end = end;
 236
 237             /* Link in the new range: */
 238             if (overlap) {
 239                 TAILQ_INSERT_BEFORE(overlap, range, rl_link);
 240             } else {
 241                 TAILQ_INSERT_TAIL(rangelist, range, rl_link);
 242             }
 243
 244             /* Check to see if any ranges can be combined (possibly including the immediately
 245              preceding range entry)
 246              */
 247             rl_collapse_neighbors(rangelist, range);
 248             break;
 249
 250         case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 251         case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
 252             break;
 253
 254         case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 255             /*
 256              * Replace the overlap with the new, larger range:
 257              */
 258             overlap->rl_start = start;
 259             overlap->rl_end = end;
 260             rl_collapse_neighbors(rangelist, overlap);
 261             break;
 262
 263         case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 264             /*
 265              * Expand the overlap area to cover the new range:
 266              */
 267             overlap->rl_end = end;
 268             rl_collapse_forwards(rangelist, overlap);
 269             break;
 270
 271         case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 272             /*
 273              * Expand the overlap area to cover the new range:
 274              */
 275             overlap->rl_start = start;
 276             rl_collapse_backwards(rangelist, overlap);
 277             break;
 278     }
 279
 280 #ifdef RL_DIAGNOSTIC
 281     rl_verify(rangelist);
 282 #endif
 283 }
 284
 285 /*
 286  * Scan a range list for an entry in a specified range (if any):
 287  *
 288  * NOTE: this returns only the FIRST overlapping range.
 289  *         There may be more than one.
 290  */
 291
 292 enum rl_overlaptype
 293 rl_scan(struct rl_head *rangelist, off_t start, off_t end, struct rl_entry **overlap)
 294 {
 295     return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
 296 }
 297
 298 static void
 299 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
 300     struct rl_entry *next_range;
 301
 302     while ((next_range = TAILQ_NEXT(range, rl_link))) {
 303         if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
 304
 305         /* Expand this range to include the next range: */
 306         range->rl_end = next_range->rl_end;
 307
 308         /* Remove the now covered range from the list: */
 309         TAILQ_REMOVE(rangelist, next_range, rl_link);
 310         hfs_free(next_range);
 311
 312 #ifdef RL_DIAGNOSTIC
 313         rl_verify(rangelist);
 314 #endif
 315     };
 316 }
 317
 318 static void
 319 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
 320     struct rl_entry *prev_range;
 321
 322     while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
 323         if (prev_range->rl_end < range->rl_start -1) {
 324 #ifdef RL_DIAGNOSTIC
 325             rl_verify(rangelist);
 326 #endif
 327             return;
 328         };
 329
 330         /* Expand this range to include the previous range: */
 331         range->rl_start = prev_range->rl_start;
 332
 333         /* Remove the now covered range from the list: */
 334         TAILQ_REMOVE(rangelist, prev_range, rl_link);
 335         hfs_free(prev_range);
 336     };
 337 }
 338
 339 static void
 340 rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
 341 {
 342     rl_collapse_forwards(rangelist, range);
 343     rl_collapse_backwards(rangelist, range);
 344 }
 345
 346 /*
 347  * In the case where b is contained by a, we return the the largest part
 348  * remaining.  The result is stored in a.
 349  */
 350 void rl_subtract(struct rl_entry *a, const struct rl_entry *b)
 351 {
 352     switch (rl_overlap(b, a->rl_start, a->rl_end)) {
 353         case RL_MATCHINGOVERLAP:
 354         case RL_OVERLAPCONTAINSRANGE:
 355             a->rl_end = a->rl_start - 1;
 356             break;
 357         case RL_OVERLAPISCONTAINED:
 358             // Keep the bigger part
 359             if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) {
 360                 // Keep left
 361                 a->rl_end = b->rl_start - 1;
 362             } else {
 363                 // Keep right
 364                 a->rl_start = b->rl_end + 1;
 365             }
 366             break;
 367         case RL_OVERLAPSTARTSBEFORE:
 368             a->rl_start = b->rl_end + 1;
 369             break;
 370         case RL_OVERLAPENDSAFTER:
 371             a->rl_end = b->rl_start - 1;
 372             break;
 373         case RL_NOOVERLAP:
 374             break;
 375     }
 376 }
 377
 378 struct rl_entry rl_make(off_t start, off_t end)
 379 {
 380     return (struct rl_entry){ .rl_start = start, .rl_end = end };
 381 }