reactos/drivers/filesystems/btrfs/extent-tree.c

   1 /* Copyright (c) Mark Harmstone 2016
   2  *
   3  * This file is part of WinBtrfs.
   4  *
   5  * WinBtrfs is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU Lesser General Public Licence as published by
   7  * the Free Software Foundation, either version 3 of the Licence, or
   8  * (at your option) any later version.
   9  *
  10  * WinBtrfs is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU Lesser General Public Licence for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public Licence
  16  * along with WinBtrfs.  If not, see <http://www.gnu.org/licenses/>. */
  17
  18 #include "btrfs_drv.h"
  19
  20 static __inline ULONG get_extent_data_len(UINT8 type) {
  21     switch (type) {
  22         case TYPE_TREE_BLOCK_REF:
  23             return sizeof(TREE_BLOCK_REF);
  24
  25         case TYPE_EXTENT_DATA_REF:
  26             return sizeof(EXTENT_DATA_REF);
  27
  28         // FIXME - TYPE_EXTENT_REF_V0
  29         // FIXME - TYPE_SHARED_BLOCK_REF
  30
  31         case TYPE_SHARED_DATA_REF:
  32             return sizeof(SHARED_DATA_REF);
  33
  34         default:
  35             return 0;
  36     }
  37 }
  38
  39 static __inline UINT64 get_extent_data_refcount(UINT8 type, void* data) {
  40     switch (type) {
  41         case TYPE_TREE_BLOCK_REF:
  42             return 1;
  43
  44         case TYPE_EXTENT_DATA_REF:
  45         {
  46             EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
  47             return edr->count;
  48         }
  49
  50         // FIXME - TYPE_EXTENT_REF_V0
  51         // FIXME - TYPE_SHARED_BLOCK_REF
  52
  53         case TYPE_SHARED_DATA_REF:
  54         {
  55             SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
  56             return sdr->count;
  57         }
  58
  59         default:
  60             return 0;
  61     }
  62 }
  63
  64 static UINT64 get_extent_data_ref_hash(EXTENT_DATA_REF* edr) {
  65     UINT32 high_crc = 0xffffffff, low_crc = 0xffffffff;
  66
  67     high_crc = calc_crc32c(high_crc, (UINT8*)&edr->root, sizeof(UINT64));
  68     low_crc = calc_crc32c(low_crc, (UINT8*)&edr->objid, sizeof(UINT64));
  69     low_crc = calc_crc32c(low_crc, (UINT8*)&edr->offset, sizeof(UINT64));
  70
  71     return ((UINT64)high_crc << 31) ^ (UINT64)low_crc;
  72 }
  73
  74 static UINT64 get_extent_hash(UINT8 type, void* data) {
  75     if (type == TYPE_EXTENT_DATA_REF) {
  76         return get_extent_data_ref_hash((EXTENT_DATA_REF*)data);
  77     } else {
  78         ERR("unhandled extent type %x\n", type);
  79         return 0;
  80     }
  81 }
  82
  83 static NTSTATUS increase_extent_refcount(device_extension* Vcb, UINT64 address, UINT64 size, UINT8 type, void* data, KEY* firstitem, UINT8 level, LIST_ENTRY* rollback) {
  84     NTSTATUS Status;
  85     KEY searchkey;
  86     traverse_ptr tp;
  87     ULONG datalen = get_extent_data_len(type), len, max_extent_item_size;
  88     EXTENT_ITEM* ei;
  89     UINT8* ptr;
  90     UINT64 inline_rc, offset;
  91     UINT8* data2;
  92     EXTENT_ITEM* newei;
  93
  94     // FIXME - handle A9s
  95
  96     if (datalen == 0) {
  97         ERR("unrecognized extent type %x\n", type);
  98         return STATUS_INTERNAL_ERROR;
  99     }
 100
 101     searchkey.obj_id = address;
 102     searchkey.obj_type = TYPE_EXTENT_ITEM;
 103     searchkey.offset = 0xffffffffffffffff;
 104
 105     Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
 106     if (!NT_SUCCESS(Status)) {
 107         ERR("error - find_item returned %08x\n", Status);
 108         return Status;
 109     }
 110
 111     // If entry doesn't exist yet, create new inline extent item
 112
 113     if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
 114         ULONG eisize;
 115         EXTENT_ITEM* ei;
 116         BOOL is_tree = type == TYPE_TREE_BLOCK_REF;
 117         UINT8* ptr;
 118
 119         eisize = sizeof(EXTENT_ITEM);
 120         if (is_tree) eisize += sizeof(EXTENT_ITEM2);
 121         eisize += sizeof(UINT8);
 122         eisize += datalen;
 123
 124         ei = ExAllocatePoolWithTag(PagedPool, eisize, ALLOC_TAG);
 125         if (!ei) {
 126             ERR("out of memory\n");
 127             return STATUS_INSUFFICIENT_RESOURCES;
 128         }
 129
 130         ei->refcount = get_extent_data_refcount(type, data);
 131         ei->generation = Vcb->superblock.generation;
 132         ei->flags = is_tree ? EXTENT_ITEM_TREE_BLOCK : EXTENT_ITEM_DATA;
 133         ptr = (UINT8*)&ei[1];
 134
 135         if (is_tree) {
 136             EXTENT_ITEM2* ei2 = (EXTENT_ITEM2*)ptr;
 137             ei2->firstitem = *firstitem;
 138             ei2->level = level;
 139             ptr = (UINT8*)&ei2[1];
 140         }
 141
 142         *ptr = type;
 143         RtlCopyMemory(ptr + 1, data, datalen);
 144
 145         if (!insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, size, ei, eisize, NULL, rollback)) {
 146             ERR("insert_tree_item failed\n");
 147             return STATUS_INTERNAL_ERROR;
 148         }
 149
 150         // FIXME - add to space list?
 151
 152         return STATUS_SUCCESS;
 153     } else if (tp.item->key.offset != size) {
 154         ERR("extent %llx exists, but with size %llx rather than %llx expected\n", tp.item->key.obj_id, tp.item->key.offset, size);
 155         return STATUS_INTERNAL_ERROR;
 156     } else if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
 157         TRACE("converting old-style extent at (%llx,%x,%llx)\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
 158
 159         Status = convert_old_data_extent(Vcb, address, size, rollback);
 160         if (!NT_SUCCESS(Status)) {
 161             ERR("convert_old_data_extent returned %08x\n", Status);
 162             return Status;
 163         }
 164
 165         return increase_extent_refcount(Vcb, address, size, type, data, firstitem, level, rollback);
 166     } else if (tp.item->size < sizeof(EXTENT_ITEM)) {
 167         ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
 168         return STATUS_INTERNAL_ERROR;
 169     }
 170
 171     ei = (EXTENT_ITEM*)tp.item->data;
 172
 173     len = tp.item->size - sizeof(EXTENT_ITEM);
 174     ptr = (UINT8*)&ei[1];
 175
 176     if (ei->flags & EXTENT_ITEM_TREE_BLOCK) {
 177         if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
 178             ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
 179             return STATUS_INTERNAL_ERROR;
 180         }
 181
 182         len -= sizeof(EXTENT_ITEM2);
 183         ptr += sizeof(EXTENT_ITEM2);
 184     }
 185
 186     inline_rc = 0;
 187
 188     // Loop through existing inline extent entries
 189
 190     while (len > 0) {
 191         UINT8 secttype = *ptr;
 192         ULONG sectlen = get_extent_data_len(secttype);
 193         UINT64 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
 194
 195         len--;
 196
 197         if (sectlen > len) {
 198             ERR("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
 199             return STATUS_INTERNAL_ERROR;
 200         }
 201
 202         if (sectlen == 0) {
 203             ERR("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
 204             return STATUS_INTERNAL_ERROR;
 205         }
 206
 207         if (secttype == TYPE_SHARED_DATA_REF) {
 208             TRACE("found shared data extent at %llx, converting\n", tp.item->key.obj_id);
 209
 210             Status = convert_shared_data_extent(Vcb, address, size, rollback);
 211             if (!NT_SUCCESS(Status)) {
 212                 ERR("convert_shared_data_extent returned %08x\n", Status);
 213                 return Status;
 214             }
 215
 216             return increase_extent_refcount(Vcb, address, size, type, data, firstitem, level, rollback);
 217         }
 218
 219         // If inline extent already present, increase refcount and return
 220
 221         if (secttype == type) {
 222             if (type == TYPE_EXTENT_DATA_REF) {
 223                 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(UINT8));
 224                 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
 225
 226                 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
 227                     UINT32 rc = get_extent_data_refcount(type, data);
 228                     EXTENT_DATA_REF* sectedr2;
 229
 230                     newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
 231                     if (!newei) {
 232                         ERR("out of memory\n");
 233                         return STATUS_INSUFFICIENT_RESOURCES;
 234                     }
 235
 236                     RtlCopyMemory(newei, tp.item->data, tp.item->size);
 237
 238                     newei->generation = Vcb->superblock.generation;
 239                     newei->refcount += rc;
 240
 241                     sectedr2 = (EXTENT_DATA_REF*)((UINT8*)newei + ((UINT8*)sectedr - tp.item->data));
 242                     sectedr2->count += rc;
 243
 244                     delete_tree_item(Vcb, &tp, rollback);
 245
 246                     if (!insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, tp.item->size, NULL, rollback)) {
 247                         ERR("insert_tree_item failed\n");
 248                         return STATUS_INTERNAL_ERROR;
 249                     }
 250
 251                     return STATUS_SUCCESS;
 252                 }
 253             } else if (type == TYPE_TREE_BLOCK_REF) {
 254                 ERR("trying to increase refcount of tree extent\n");
 255                 return STATUS_INTERNAL_ERROR;
 256             } else {
 257                 ERR("unhandled extent type %x\n", type);
 258                 return STATUS_INTERNAL_ERROR;
 259             }
 260         }
 261
 262         len -= sectlen;
 263         ptr += sizeof(UINT8) + sectlen;
 264         inline_rc += sectcount;
 265     }
 266
 267     offset = get_extent_hash(type, data);
 268
 269     max_extent_item_size = (Vcb->superblock.node_size >> 4) - sizeof(leaf_node);
 270
 271     // If we can, add entry as inline extent item
 272
 273     if (inline_rc == ei->refcount && tp.item->size + sizeof(UINT8) + datalen < max_extent_item_size) {
 274         len = tp.item->size - sizeof(EXTENT_ITEM);
 275         ptr = (UINT8*)&ei[1];
 276
 277         if (ei->flags & EXTENT_ITEM_TREE_BLOCK) {
 278             len -= sizeof(EXTENT_ITEM2);
 279             ptr += sizeof(EXTENT_ITEM2);
 280         }
 281
 282         while (len > 0) {
 283             UINT8 secttype = *ptr;
 284             ULONG sectlen = get_extent_data_len(secttype);
 285
 286             if (secttype > type)
 287                 break;
 288
 289             len--;
 290
 291             if (secttype == type) {
 292                 UINT64 sectoff = get_extent_hash(secttype, ptr + 1);
 293
 294                 if (sectoff > offset)
 295                     break;
 296             }
 297
 298             len -= sectlen;
 299             ptr += sizeof(UINT8) + sectlen;
 300         }
 301
 302         newei = ExAllocatePoolWithTag(PagedPool, tp.item->size + sizeof(UINT8) + datalen, ALLOC_TAG);
 303         RtlCopyMemory(newei, tp.item->data, ptr - tp.item->data);
 304
 305         newei->generation = Vcb->superblock.generation;
 306         newei->refcount += get_extent_data_refcount(type, data);
 307
 308         if (len > 0)
 309             RtlCopyMemory((UINT8*)newei + (ptr - tp.item->data) + sizeof(UINT8) + datalen, ptr, len + 1);
 310
 311         ptr = (ptr - tp.item->data) + (UINT8*)newei;
 312
 313         *ptr = type;
 314         RtlCopyMemory(ptr + 1, data, datalen);
 315
 316         delete_tree_item(Vcb, &tp, rollback);
 317
 318         if (!insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, tp.item->size + sizeof(UINT8) + datalen, NULL, rollback)) {
 319             ERR("insert_tree_item failed\n");
 320             return STATUS_INTERNAL_ERROR;
 321         }
 322
 323         return STATUS_SUCCESS;
 324     }
 325
 326     // Look for existing non-inline entry, and increase refcount if found
 327
 328     if (inline_rc != ei->refcount) {
 329         traverse_ptr tp2;
 330
 331         searchkey.obj_id = address;
 332         searchkey.obj_type = type;
 333         searchkey.offset = offset;
 334
 335         Status = find_item(Vcb, Vcb->extent_root, &tp2, &searchkey, FALSE);
 336         if (!NT_SUCCESS(Status)) {
 337             ERR("error - find_item returned %08x\n", Status);
 338             return Status;
 339         }
 340
 341         if (!keycmp(&tp.item->key, &searchkey)) {
 342             if (tp.item->size < datalen) {
 343                 ERR("(%llx,%x,%llx) was %x bytes, expecting %x\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, tp.item->size, datalen);
 344                 return STATUS_INTERNAL_ERROR;
 345             }
 346
 347             data2 = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
 348             RtlCopyMemory(data2, tp2.item->data, tp2.item->size);
 349
 350             if (type == TYPE_EXTENT_DATA_REF) {
 351                 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data2;
 352
 353                 edr->count += get_extent_data_refcount(type, data);
 354             } else if (type == TYPE_TREE_BLOCK_REF) {
 355                 ERR("trying to increase refcount of tree extent\n");
 356                 return STATUS_INTERNAL_ERROR;
 357             } else {
 358                 ERR("unhandled extent type %x\n", type);
 359                 return STATUS_INTERNAL_ERROR;
 360             }
 361
 362             delete_tree_item(Vcb, &tp2, rollback);
 363
 364             if (!insert_tree_item(Vcb, Vcb->extent_root, tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, data2, tp2.item->size, NULL, rollback)) {
 365                 ERR("insert_tree_item failed\n");
 366                 return STATUS_INTERNAL_ERROR;
 367             }
 368
 369             newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
 370             RtlCopyMemory(newei, tp.item->data, tp.item->size);
 371
 372             newei->generation = Vcb->superblock.generation;
 373             newei->refcount += get_extent_data_refcount(type, data);
 374
 375             delete_tree_item(Vcb, &tp, rollback);
 376
 377             if (!insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, tp.item->size, NULL, rollback)) {
 378                 ERR("insert_tree_item failed\n");
 379                 return STATUS_INTERNAL_ERROR;
 380             }
 381
 382             return STATUS_SUCCESS;
 383         }
 384     }
 385
 386     // Otherwise, add new non-inline entry
 387
 388     data2 = ExAllocatePoolWithTag(PagedPool, datalen, ALLOC_TAG);
 389     RtlCopyMemory(data2, data, datalen);
 390
 391     if (!insert_tree_item(Vcb, Vcb->extent_root, address, type, offset, data2, datalen, NULL, rollback)) {
 392         ERR("insert_tree_item failed\n");
 393         return STATUS_INTERNAL_ERROR;
 394     }
 395
 396     newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
 397     RtlCopyMemory(newei, tp.item->data, tp.item->size);
 398
 399     newei->generation = Vcb->superblock.generation;
 400     newei->refcount += get_extent_data_refcount(type, data);
 401
 402     delete_tree_item(Vcb, &tp, rollback);
 403
 404     if (!insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, tp.item->size, NULL, rollback)) {
 405         ERR("insert_tree_item failed\n");
 406         return STATUS_INTERNAL_ERROR;
 407     }
 408
 409     return STATUS_SUCCESS;
 410 }
 411
 412 NTSTATUS increase_extent_refcount_data(device_extension* Vcb, UINT64 address, UINT64 size, root* subvol, UINT64 inode, UINT64 offset, UINT32 refcount, LIST_ENTRY* rollback) {
 413     EXTENT_DATA_REF edr;
 414
 415     edr.root = subvol->id;
 416     edr.objid = inode;
 417     edr.offset = offset;
 418     edr.count = refcount;
 419
 420     return increase_extent_refcount(Vcb, address, size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, rollback);
 421 }
 422
 423 void decrease_chunk_usage(chunk* c, UINT64 delta) {
 424     c->used -= delta;
 425
 426     TRACE("decreasing size of chunk %llx by %llx\n", c->offset, delta);
 427 }
 428
 429 static NTSTATUS remove_extent(device_extension* Vcb, UINT64 address, UINT64 size, LIST_ENTRY* changed_sector_list) {
 430     chunk* c;
 431     LIST_ENTRY* le;
 432
 433     if (changed_sector_list) {
 434         changed_sector* sc = ExAllocatePoolWithTag(PagedPool, sizeof(changed_sector), ALLOC_TAG);
 435         if (!sc) {
 436             ERR("out of memory\n");
 437             return STATUS_INSUFFICIENT_RESOURCES;
 438         }
 439
 440         sc->ol.key = address;
 441         sc->checksums = NULL;
 442         sc->length = size / Vcb->superblock.sector_size;
 443
 444         sc->deleted = TRUE;
 445
 446         insert_into_ordered_list(changed_sector_list, &sc->ol);
 447     }
 448
 449     c = NULL;
 450     le = Vcb->chunks.Flink;
 451     while (le != &Vcb->chunks) {
 452         c = CONTAINING_RECORD(le, chunk, list_entry);
 453
 454         if (address >= c->offset && address + size < c->offset + c->chunk_item->size)
 455             break;
 456
 457         le = le->Flink;
 458     }
 459     if (le == &Vcb->chunks) c = NULL;
 460
 461     if (c) {
 462         decrease_chunk_usage(c, size);
 463
 464         add_to_space_list(c, address, size, SPACE_TYPE_DELETING);
 465     }
 466
 467     return STATUS_SUCCESS;
 468 }
 469
 470 static NTSTATUS decrease_extent_refcount(device_extension* Vcb, UINT64 address, UINT64 size, UINT8 type, void* data, KEY* firstitem,
 471                                          UINT8 level, LIST_ENTRY* changed_sector_list, LIST_ENTRY* rollback) {
 472     KEY searchkey;
 473     NTSTATUS Status;
 474     traverse_ptr tp, tp2;
 475     EXTENT_ITEM* ei;
 476     ULONG len;
 477     UINT64 inline_rc, offset;
 478     UINT8* ptr;
 479     UINT32 rc = get_extent_data_refcount(type, data);
 480     ULONG datalen = get_extent_data_len(type);
 481
 482     // FIXME - handle trees
 483
 484     searchkey.obj_id = address;
 485     searchkey.obj_type = TYPE_EXTENT_ITEM;
 486     searchkey.offset = 0xffffffffffffffff;
 487
 488     Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
 489     if (!NT_SUCCESS(Status)) {
 490         ERR("error - find_item returned %08x\n", Status);
 491         return Status;
 492     }
 493
 494     if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
 495         ERR("could not find EXTENT_ITEM for address %llx\n", address);
 496         return STATUS_INTERNAL_ERROR;
 497     }
 498
 499     if (tp.item->key.offset != size) {
 500         ERR("extent %llx had length %llx, not %llx as expected\n", address, tp.item->key.offset, size);
 501         return STATUS_INTERNAL_ERROR;
 502     }
 503
 504     if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
 505         TRACE("converting old-style extent at (%llx,%x,%llx)\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
 506
 507         Status = convert_old_data_extent(Vcb, address, size, rollback);
 508         if (!NT_SUCCESS(Status)) {
 509             ERR("convert_old_data_extent returned %08x\n", Status);
 510             return Status;
 511         }
 512
 513         return decrease_extent_refcount(Vcb, address, size, type, data, firstitem, level, changed_sector_list, rollback);
 514     }
 515
 516     if (tp.item->size < sizeof(EXTENT_ITEM)) {
 517         ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
 518         return STATUS_INTERNAL_ERROR;
 519     }
 520
 521     ei = (EXTENT_ITEM*)tp.item->data;
 522
 523     len = tp.item->size - sizeof(EXTENT_ITEM);
 524     ptr = (UINT8*)&ei[1];
 525
 526     if (ei->flags & EXTENT_ITEM_TREE_BLOCK) {
 527         if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
 528             ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
 529             return STATUS_INTERNAL_ERROR;
 530         }
 531
 532         len -= sizeof(EXTENT_ITEM2);
 533         ptr += sizeof(EXTENT_ITEM2);
 534     }
 535
 536     if (ei->refcount < rc) {
 537         ERR("error - extent has refcount %llx, trying to reduce by %x\n", ei->refcount, rc);
 538         return STATUS_INTERNAL_ERROR;
 539     }
 540
 541     inline_rc = 0;
 542
 543     // Loop through inline extent entries
 544
 545     while (len > 0) {
 546         UINT8 secttype = *ptr;
 547         ULONG sectlen = get_extent_data_len(secttype);
 548         UINT64 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
 549
 550         len--;
 551
 552         if (sectlen > len) {
 553             ERR("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
 554             return STATUS_INTERNAL_ERROR;
 555         }
 556
 557         if (sectlen == 0) {
 558             ERR("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
 559             return STATUS_INTERNAL_ERROR;
 560         }
 561
 562         if (secttype == TYPE_SHARED_DATA_REF) {
 563             TRACE("found shared data extent at %llx, converting\n", tp.item->key.obj_id);
 564
 565             Status = convert_shared_data_extent(Vcb, address, size, rollback);
 566             if (!NT_SUCCESS(Status)) {
 567                 ERR("convert_shared_data_extent returned %08x\n", Status);
 568                 return Status;
 569             }
 570
 571             return decrease_extent_refcount(Vcb, address, size, type, data, firstitem, level, changed_sector_list, rollback);
 572         }
 573
 574         if (secttype == type) {
 575             if (type == TYPE_EXTENT_DATA_REF) {
 576                 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(UINT8));
 577                 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
 578                 ULONG neweilen;
 579                 EXTENT_ITEM* newei;
 580
 581                 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
 582                     if (ei->refcount == edr->count) {
 583                         Status = remove_extent(Vcb, address, size, changed_sector_list);
 584                         if (!NT_SUCCESS(Status)) {
 585                             ERR("remove_extent returned %08x\n", Status);
 586                             return Status;
 587                         }
 588
 589                         delete_tree_item(Vcb, &tp, rollback);
 590                         return STATUS_SUCCESS;
 591                     }
 592
 593                     if (sectedr->count < edr->count) {
 594                         ERR("error - extent section has refcount %x, trying to reduce by %x\n", sectedr->count, edr->count);
 595                         return STATUS_INTERNAL_ERROR;
 596                     }
 597
 598                     if (sectedr->count > edr->count)    // reduce section refcount
 599                         neweilen = tp.item->size;
 600                     else                                // remove section entirely
 601                         neweilen = tp.item->size - sizeof(UINT8) - sectlen;
 602
 603                     newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
 604                     if (!newei) {
 605                         ERR("out of memory\n");
 606                         return STATUS_INSUFFICIENT_RESOURCES;
 607                     }
 608
 609                     if (sectedr->count > edr->count) {
 610                         EXTENT_DATA_REF* newedr = (EXTENT_DATA_REF*)((UINT8*)newei + ((UINT8*)sectedr - tp.item->data));
 611
 612                         RtlCopyMemory(newei, ei, neweilen);
 613
 614                         newedr->count -= rc;
 615                     } else {
 616                         RtlCopyMemory(newei, ei, ptr - tp.item->data);
 617
 618                         if (len > sectlen)
 619                             RtlCopyMemory((UINT8*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(UINT8), len - sectlen);
 620                     }
 621
 622                     newei->generation = Vcb->superblock.generation;
 623                     newei->refcount -= rc;
 624
 625                     delete_tree_item(Vcb, &tp, rollback);
 626
 627                     if (!insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, neweilen, NULL, rollback)) {
 628                         ERR("insert_tree_item failed\n");
 629                         return STATUS_INTERNAL_ERROR;
 630                     }
 631
 632                     return STATUS_SUCCESS;
 633                 }
 634 //             } else if (type == TYPE_TREE_BLOCK_REF) {
 635 //                 ERR("trying to increase refcount of tree extent\n");
 636 //                 return STATUS_INTERNAL_ERROR;
 637             } else {
 638                 ERR("unhandled extent type %x\n", type);
 639                 return STATUS_INTERNAL_ERROR;
 640             }
 641         }
 642
 643         len -= sectlen;
 644         ptr += sizeof(UINT8) + sectlen;
 645         inline_rc += sectcount;
 646     }
 647
 648     if (inline_rc == ei->refcount) {
 649         ERR("entry not found in inline extent item for address %llx\n", address);
 650         return STATUS_INTERNAL_ERROR;
 651     }
 652
 653     offset = get_extent_hash(type, data);
 654
 655     searchkey.obj_id = address;
 656     searchkey.obj_type = type;
 657     searchkey.offset = offset;
 658
 659     Status = find_item(Vcb, Vcb->extent_root, &tp2, &searchkey, FALSE);
 660     if (!NT_SUCCESS(Status)) {
 661         ERR("error - find_item returned %08x\n", Status);
 662         return Status;
 663     }
 664
 665     if (keycmp(&tp2.item->key, &searchkey)) {
 666         ERR("(%llx,%x,%llx) not found\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset);
 667         return STATUS_INTERNAL_ERROR;
 668     }
 669
 670     if (tp2.item->size < datalen) {
 671         ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, datalen);
 672         return STATUS_INTERNAL_ERROR;
 673     }
 674
 675     if (type == TYPE_EXTENT_DATA_REF) {
 676         EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)tp2.item->data;
 677         EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
 678         EXTENT_ITEM* newei;
 679
 680         if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
 681             if (ei->refcount == edr->count) {
 682                 Status = remove_extent(Vcb, address, size, changed_sector_list);
 683                 if (!NT_SUCCESS(Status)) {
 684                     ERR("remove_extent returned %08x\n", Status);
 685                     return Status;
 686                 }
 687
 688                 delete_tree_item(Vcb, &tp, rollback);
 689                 delete_tree_item(Vcb, &tp2, rollback);
 690                 return STATUS_SUCCESS;
 691             }
 692
 693             if (sectedr->count < edr->count) {
 694                 ERR("error - extent section has refcount %x, trying to reduce by %x\n", sectedr->count, edr->count);
 695                 return STATUS_INTERNAL_ERROR;
 696             }
 697
 698             delete_tree_item(Vcb, &tp2, rollback);
 699
 700             if (sectedr->count > edr->count) {
 701                 EXTENT_DATA_REF* newedr = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
 702
 703                 if (!newedr) {
 704                     ERR("out of memory\n");
 705                     return STATUS_INSUFFICIENT_RESOURCES;
 706                 }
 707
 708                 RtlCopyMemory(newedr, sectedr, tp2.item->size);
 709
 710                 newedr->count -= edr->count;
 711
 712                 if (!insert_tree_item(Vcb, Vcb->extent_root, tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, newedr, tp2.item->size, NULL, rollback)) {
 713                     ERR("insert_tree_item failed\n");
 714                     return STATUS_INTERNAL_ERROR;
 715                 }
 716             }
 717
 718             newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
 719             if (!newei) {
 720                 ERR("out of memory\n");
 721                 return STATUS_INSUFFICIENT_RESOURCES;
 722             }
 723
 724             RtlCopyMemory(newei, tp.item->data, tp.item->size);
 725
 726             newei->generation = Vcb->superblock.generation;
 727             newei->refcount -= rc;
 728
 729             delete_tree_item(Vcb, &tp, rollback);
 730
 731             if (!insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, tp.item->size, NULL, rollback)) {
 732                 ERR("insert_tree_item failed\n");
 733                 return STATUS_INTERNAL_ERROR;
 734             }
 735
 736             return STATUS_SUCCESS;
 737         } else {
 738             ERR("error - hash collision?\n");
 739             return STATUS_INTERNAL_ERROR;
 740         }
 741 //     } else if (type == TYPE_TREE_BLOCK_REF) {
 742 //         ERR("trying to increase refcount of tree extent\n");
 743 //         return STATUS_INTERNAL_ERROR;
 744     } else {
 745         ERR("unhandled extent type %x\n", type);
 746         return STATUS_INTERNAL_ERROR;
 747     }
 748 }
 749
 750 NTSTATUS decrease_extent_refcount_data(device_extension* Vcb, UINT64 address, UINT64 size, root* subvol, UINT64 inode,
 751                                        UINT64 offset, UINT32 refcount, LIST_ENTRY* changed_sector_list, LIST_ENTRY* rollback) {
 752     EXTENT_DATA_REF edr;
 753
 754     edr.root = subvol->id;
 755     edr.objid = inode;
 756     edr.offset = offset;
 757     edr.count = refcount;
 758
 759     return decrease_extent_refcount(Vcb, address, size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, changed_sector_list, rollback);
 760 }
 761
 762 typedef struct {
 763     UINT8 type;
 764     void* data;
 765     BOOL allocated;
 766     UINT64 hash;
 767     LIST_ENTRY list_entry;
 768 } extent_ref;
 769
 770 static void free_extent_refs(LIST_ENTRY* extent_refs) {
 771     while (!IsListEmpty(extent_refs)) {
 772         LIST_ENTRY* le = RemoveHeadList(extent_refs);
 773         extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
 774
 775         if (er->allocated)
 776             ExFreePool(er->data);
 777
 778         ExFreePool(er);
 779     }
 780 }
 781
 782 static NTSTATUS add_data_extent_ref(LIST_ENTRY* extent_refs, UINT64 tree_id, UINT64 obj_id, UINT64 offset) {
 783     extent_ref* er2;
 784     EXTENT_DATA_REF* edr;
 785     LIST_ENTRY* le;
 786
 787     if (!IsListEmpty(extent_refs)) {
 788         le = extent_refs->Flink;
 789
 790         while (le != extent_refs) {
 791             extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
 792
 793             if (er->type == TYPE_EXTENT_DATA_REF) {
 794                 edr = (EXTENT_DATA_REF*)er->data;
 795
 796                 if (edr->root == tree_id && edr->objid == obj_id && edr->offset == offset) {
 797                     edr->count++;
 798                     return STATUS_SUCCESS;
 799                 }
 800             }
 801
 802             le = le->Flink;
 803         }
 804     }
 805
 806     er2 = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
 807     if (!er2) {
 808         ERR("out of memory\n");
 809         return STATUS_INSUFFICIENT_RESOURCES;
 810     }
 811
 812     edr = ExAllocatePoolWithTag(PagedPool, sizeof(EXTENT_DATA_REF), ALLOC_TAG);
 813     if (!edr) {
 814         ERR("out of memory\n");
 815         ExFreePool(er2);
 816         return STATUS_INSUFFICIENT_RESOURCES;
 817     }
 818
 819     edr->root = tree_id;
 820     edr->objid = obj_id;
 821     edr->offset = offset;
 822     edr->count = 1; // FIXME - not necessarily
 823
 824     er2->type = TYPE_EXTENT_DATA_REF;
 825     er2->data = edr;
 826     er2->allocated = TRUE;
 827
 828     InsertTailList(extent_refs, &er2->list_entry);
 829
 830     return STATUS_SUCCESS;
 831 }
 832
 833 static NTSTATUS construct_extent_item(device_extension* Vcb, UINT64 address, UINT64 size, UINT64 flags, LIST_ENTRY* extent_refs, LIST_ENTRY* rollback) {
 834     LIST_ENTRY *le, *next_le;
 835     UINT64 refcount;
 836     ULONG inline_len;
 837     BOOL all_inline = TRUE;
 838     extent_ref* first_noninline;
 839     EXTENT_ITEM* ei;
 840     UINT8* siptr;
 841
 842     if (IsListEmpty(extent_refs)) {
 843         WARN("no extent refs found\n");
 844         return STATUS_SUCCESS;
 845     }
 846
 847     refcount = 0;
 848     inline_len = sizeof(EXTENT_ITEM);
 849
 850     le = extent_refs->Flink;
 851     while (le != extent_refs) {
 852         extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
 853         UINT64 rc;
 854
 855         next_le = le->Flink;
 856
 857         rc = get_extent_data_refcount(er->type, er->data);
 858
 859         if (rc == 0) {
 860             if (er->allocated)
 861                 ExFreePool(er->data);
 862
 863             RemoveEntryList(&er->list_entry);
 864
 865             ExFreePool(er);
 866         } else {
 867             ULONG extlen = get_extent_data_len(er->type);
 868
 869             refcount += rc;
 870
 871             if (er->type == TYPE_EXTENT_DATA_REF)
 872                 er->hash = get_extent_data_ref_hash(er->data);
 873             else
 874                 er->hash = 0;
 875
 876             if (all_inline) {
 877                 if (inline_len + 1 + extlen > Vcb->superblock.node_size / 4) {
 878                     all_inline = FALSE;
 879                     first_noninline = er;
 880                 } else
 881                     inline_len += extlen + 1;
 882             }
 883         }
 884
 885         le = next_le;
 886     }
 887
 888     ei = ExAllocatePoolWithTag(PagedPool, inline_len, ALLOC_TAG);
 889     if (!ei) {
 890         ERR("out of memory\n");
 891         return STATUS_INSUFFICIENT_RESOURCES;
 892     }
 893
 894     ei->refcount = refcount;
 895     ei->generation = Vcb->superblock.generation;
 896     ei->flags = flags;
 897
 898     // Do we need to sort the inline extent refs? The Linux driver doesn't seem to bother.
 899
 900     siptr = (UINT8*)&ei[1];
 901     le = extent_refs->Flink;
 902     while (le != extent_refs) {
 903         extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
 904         ULONG extlen = get_extent_data_len(er->type);
 905
 906         if (!all_inline && er == first_noninline)
 907             break;
 908
 909         *siptr = er->type;
 910         siptr++;
 911
 912         if (extlen > 0) {
 913             RtlCopyMemory(siptr, er->data, extlen);
 914             siptr += extlen;
 915         }
 916
 917         le = le->Flink;
 918     }
 919
 920     if (!insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, size, ei, inline_len, NULL, rollback)) {
 921         ERR("error - failed to insert item\n");
 922         ExFreePool(ei);
 923         return STATUS_INTERNAL_ERROR;
 924     }
 925
 926     if (!all_inline) {
 927         le = &first_noninline->list_entry;
 928
 929         while (le != extent_refs) {
 930             extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
 931
 932             if (!insert_tree_item(Vcb, Vcb->extent_root, address, er->type, er->hash, er->data, get_extent_data_len(er->type), NULL, rollback)) {
 933                 ERR("error - failed to insert item\n");
 934                 return STATUS_INTERNAL_ERROR;
 935             }
 936
 937             er->allocated = FALSE;
 938
 939             le = le->Flink;
 940         }
 941     }
 942
 943     return STATUS_SUCCESS;
 944 }
 945
 946 static NTSTATUS populate_extent_refs_from_tree(device_extension* Vcb, UINT64 tree_address, UINT64 extent_address, LIST_ENTRY* extent_refs) {
 947     UINT8* buf;
 948     tree_header* th;
 949     NTSTATUS Status;
 950
 951     buf = ExAllocatePoolWithTag(PagedPool, Vcb->superblock.node_size, ALLOC_TAG);
 952     if (!buf) {
 953         ERR("out of memory\n");
 954         return STATUS_INSUFFICIENT_RESOURCES;
 955     }
 956
 957     Status = read_tree(Vcb, tree_address, buf);
 958     if (!NT_SUCCESS(Status)) {
 959         ERR("read_tree returned %08x\n", Status);
 960         ExFreePool(buf);
 961         return Status;
 962     }
 963
 964     th = (tree_header*)buf;
 965
 966     if (th->level == 0) {
 967         UINT32 i;
 968         leaf_node* ln = (leaf_node*)&th[1];
 969
 970         for (i = 0; i < th->num_items; i++) {
 971             if (ln[i].key.obj_type == TYPE_EXTENT_DATA && ln[i].size >= sizeof(EXTENT_DATA) && ln[i].offset + ln[i].size <= Vcb->superblock.node_size - sizeof(tree_header)) {
 972                 EXTENT_DATA* ed = (EXTENT_DATA*)(((UINT8*)&th[1]) + ln[i].offset);
 973
 974                 if ((ed->type == EXTENT_TYPE_REGULAR || ed->type == EXTENT_TYPE_PREALLOC) && ln[i].size >= sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
 975                     EXTENT_DATA2* ed2 = (EXTENT_DATA2*)&ed->data[0];
 976
 977                     if (ed2->address == extent_address) {
 978                         Status = add_data_extent_ref(extent_refs, th->tree_id, ln[i].key.obj_id, ln[i].key.offset);
 979                         if (!NT_SUCCESS(Status)) {
 980                             ERR("add_data_extent_ref returned %08x\n", Status);
 981                             ExFreePool(buf);
 982                             return Status;
 983                         }
 984                     }
 985                 }
 986             }
 987         }
 988     } else
 989         WARN("shared data ref pointed to tree of level %x\n", th->level);
 990
 991     ExFreePool(buf);
 992
 993     return STATUS_SUCCESS;
 994 }
 995
 996 NTSTATUS convert_shared_data_extent(device_extension* Vcb, UINT64 address, UINT64 size, LIST_ENTRY* rollback) {
 997     KEY searchkey;
 998     traverse_ptr tp;
 999     LIST_ENTRY extent_refs;
1000     LIST_ENTRY *le, *next_le;
1001     EXTENT_ITEM* ei;
1002     UINT64 eiflags, inline_rc;
1003     UINT8* siptr;
1004     ULONG len;
1005     NTSTATUS Status;
1006
1007     searchkey.obj_id = address;
1008     searchkey.obj_type = TYPE_EXTENT_ITEM;
1009     searchkey.offset = size;
1010
1011     Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
1012     if (!NT_SUCCESS(Status)) {
1013         ERR("error - find_item returned %08x\n", Status);
1014         return Status;
1015     }
1016
1017     if (keycmp(&tp.item->key, &searchkey)) {
1018         WARN("extent item not found for address %llx, size %llx\n", address, size);
1019         return STATUS_SUCCESS;
1020     }
1021
1022     if (tp.item->size < sizeof(EXTENT_ITEM)) {
1023         ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1024         return STATUS_INTERNAL_ERROR;
1025     }
1026
1027     ei = (EXTENT_ITEM*)tp.item->data;
1028     len = tp.item->size - sizeof(EXTENT_ITEM);
1029     eiflags = ei->flags;
1030
1031     InitializeListHead(&extent_refs);
1032
1033     inline_rc = 0;
1034     siptr = (UINT8*)&ei[1];
1035
1036     do {
1037         extent_ref* er;
1038         ULONG extlen;
1039
1040         extlen = get_extent_data_len(*siptr);
1041
1042         if (extlen == 0) {
1043             ERR("unrecognized extent subitem %x\n", *siptr);
1044             free_extent_refs(&extent_refs);
1045             return STATUS_INTERNAL_ERROR;
1046         }
1047
1048         if (extlen > len - 1) {
1049             ERR("extent %llx was truncated\n", address);
1050             free_extent_refs(&extent_refs);
1051             return STATUS_INTERNAL_ERROR;
1052         }
1053
1054         er = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
1055         if (!er) {
1056             ERR("out of memory\n");
1057             return STATUS_INSUFFICIENT_RESOURCES;
1058         }
1059
1060         er->type = *siptr;
1061
1062         er->data = ExAllocatePoolWithTag(PagedPool, extlen, ALLOC_TAG);
1063         if (!er->data) {
1064             ERR("out of memory\n");
1065             ExFreePool(er);
1066             return STATUS_INSUFFICIENT_RESOURCES;
1067         }
1068
1069         RtlCopyMemory(er->data, siptr+1, extlen);
1070         er->allocated = TRUE;
1071
1072         InsertTailList(&extent_refs, &er->list_entry);
1073
1074         siptr += extlen;
1075         len -= extlen + 1;
1076
1077         inline_rc += get_extent_data_refcount(er->type, er->data);
1078     } while (len > 0);
1079
1080     delete_tree_item(Vcb, &tp, rollback);
1081
1082     if (inline_rc < ei->refcount) {
1083         BOOL b;
1084         traverse_ptr next_tp;
1085
1086         do {
1087             b = find_next_item(Vcb, &tp, &next_tp, FALSE);
1088
1089             if (tp.item->key.obj_id == address) {
1090                 ULONG extlen;
1091
1092                 extlen = get_extent_data_len(tp.item->key.obj_type);
1093
1094                 if (extlen != 0 && tp.item->size >= extlen) {
1095                     extent_ref* er = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
1096                     if (!er) {
1097                         ERR("out of memory\n");
1098                         return STATUS_INSUFFICIENT_RESOURCES;
1099                     }
1100
1101                     er->type = tp.item->key.obj_type;
1102
1103                     er->data = ExAllocatePoolWithTag(PagedPool, extlen, ALLOC_TAG);
1104                     if (!er->data) {
1105                         ERR("out of memory\n");
1106                         ExFreePool(er);
1107                         return STATUS_INSUFFICIENT_RESOURCES;
1108                     }
1109
1110                     RtlCopyMemory(er->data, siptr+1, extlen);
1111                     er->allocated = TRUE;
1112
1113                     InsertTailList(&extent_refs, &er->list_entry);
1114
1115                     delete_tree_item(Vcb, &tp, rollback);
1116                 }
1117             }
1118
1119             if (b) {
1120                 tp = next_tp;
1121
1122                 if (tp.item->key.obj_id > address)
1123                     break;
1124             }
1125         } while (b);
1126     }
1127
1128     le = extent_refs.Flink;
1129     while (le != &extent_refs) {
1130         extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
1131         next_le = le->Flink;
1132
1133         if (er->type == TYPE_SHARED_DATA_REF) {
1134             SHARED_DATA_REF* sdr = er->data;
1135
1136             Status = populate_extent_refs_from_tree(Vcb, sdr->offset, address, &extent_refs);
1137             if (!NT_SUCCESS(Status)) {
1138                 ERR("populate_extent_refs_from_tree returned %08x\n", Status);
1139                 free_extent_refs(&extent_refs);
1140                 return Status;
1141             }
1142
1143             RemoveEntryList(&er->list_entry);
1144
1145             if (er->allocated)
1146                 ExFreePool(er->data);
1147
1148             ExFreePool(er);
1149         }
1150         // FIXME - also do for SHARED_BLOCK_REF?
1151
1152         le = next_le;
1153     }
1154
1155     Status = construct_extent_item(Vcb, address, size, eiflags, &extent_refs, rollback);
1156     if (!NT_SUCCESS(Status)) {
1157         ERR("construct_extent_item returned %08x\n", Status);
1158         free_extent_refs(&extent_refs);
1159         return Status;
1160     }
1161
1162     free_extent_refs(&extent_refs);
1163
1164     return STATUS_SUCCESS;
1165 }
1166
1167 NTSTATUS convert_old_data_extent(device_extension* Vcb, UINT64 address, UINT64 size, LIST_ENTRY* rollback) {
1168     KEY searchkey;
1169     traverse_ptr tp, next_tp;
1170     BOOL b;
1171     LIST_ENTRY extent_refs;
1172     NTSTATUS Status;
1173
1174     searchkey.obj_id = address;
1175     searchkey.obj_type = TYPE_EXTENT_ITEM;
1176     searchkey.offset = size;
1177
1178     Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
1179     if (!NT_SUCCESS(Status)) {
1180         ERR("error - find_item returned %08x\n", Status);
1181         return Status;
1182     }
1183
1184     if (keycmp(&tp.item->key, &searchkey)) {
1185         WARN("extent item not found for address %llx, size %llx\n", address, size);
1186         return STATUS_SUCCESS;
1187     }
1188
1189     if (tp.item->size != sizeof(EXTENT_ITEM_V0)) {
1190         TRACE("extent does not appear to be old - returning STATUS_SUCCESS\n");
1191         return STATUS_SUCCESS;
1192     }
1193
1194     delete_tree_item(Vcb, &tp, rollback);
1195
1196     searchkey.obj_id = address;
1197     searchkey.obj_type = TYPE_EXTENT_REF_V0;
1198     searchkey.offset = 0;
1199
1200     Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
1201     if (!NT_SUCCESS(Status)) {
1202         ERR("error - find_item returned %08x\n", Status);
1203         return Status;
1204     }
1205
1206     InitializeListHead(&extent_refs);
1207
1208     do {
1209         b = find_next_item(Vcb, &tp, &next_tp, FALSE);
1210
1211         if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type) {
1212             Status = populate_extent_refs_from_tree(Vcb, tp.item->key.offset, address, &extent_refs);
1213             if (!NT_SUCCESS(Status)) {
1214                 ERR("populate_extent_refs_from_tree returned %08x\n", Status);
1215                 return Status;
1216             }
1217
1218             delete_tree_item(Vcb, &tp, rollback);
1219         }
1220
1221         if (b) {
1222             tp = next_tp;
1223
1224             if (tp.item->key.obj_id > searchkey.obj_id || tp.item->key.obj_type > searchkey.obj_type)
1225                 break;
1226         }
1227     } while (b);
1228
1229     Status = construct_extent_item(Vcb, address, size, EXTENT_ITEM_DATA, &extent_refs, rollback);
1230     if (!NT_SUCCESS(Status)) {
1231         ERR("construct_extent_item returned %08x\n", Status);
1232         free_extent_refs(&extent_refs);
1233         return Status;
1234     }
1235
1236     free_extent_refs(&extent_refs);
1237
1238     return STATUS_SUCCESS;
1239 }