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