ReactOS  0.4.13-dev-235-g7373cb3
free-space.c
Go to the documentation of this file.
1 /* Copyright (c) Mark Harmstone 2016-17
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 // Number of increments in the size of each cache inode, in sectors. Should
21 // this be a constant number of sectors, a constant 256 KB, or what?
22 #define CACHE_INCREMENTS 64
23 
26  fcb* fcb;
27 
29  if (!NT_SUCCESS(Status)) {
30  ERR("open_fcb returned %08x\n", Status);
31  return Status;
32  }
33 
35 
36  if (fcb->inode_item.st_size > 0) {
37  Status = excise_extents(fcb->Vcb, fcb, 0, sector_align(fcb->inode_item.st_size, fcb->Vcb->superblock.sector_size), Irp, rollback);
38  if (!NT_SUCCESS(Status)) {
39  ERR("excise_extents returned %08x\n", Status);
40  return Status;
41  }
42  }
43 
44  fcb->deleted = TRUE;
45 
46  Status = flush_fcb(fcb, FALSE, batchlist, Irp);
47  if (!NT_SUCCESS(Status)) {
48  ERR("flush_fcb returned %08x\n", Status);
49  free_fcb(fcb);
50  return Status;
51  }
52 
53  free_fcb(fcb);
54 
55  return STATUS_SUCCESS;
56 }
57 
59  KEY searchkey;
60  traverse_ptr tp, next_tp;
62  BOOL b;
64 
66 
67  searchkey.obj_id = FREE_SPACE_CACHE_ID;
68  searchkey.obj_type = 0;
69  searchkey.offset = 0;
70 
71  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
72  if (!NT_SUCCESS(Status)) {
73  ERR("error - find_item returned %08x\n", Status);
74  return Status;
75  }
76 
77  do {
78  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))
79  break;
80 
81  if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type) {
83  if (!NT_SUCCESS(Status)) {
84  ERR("delete_tree_item returned %08x\n", Status);
85  return Status;
86  }
87 
88  if (tp.item->size >= sizeof(FREE_SPACE_ITEM)) {
90 
91  if (fsi->key.obj_type != TYPE_INODE_ITEM)
92  WARN("key (%llx,%x,%llx) does not point to an INODE_ITEM\n", fsi->key.obj_id, fsi->key.obj_type, fsi->key.offset);
93  else {
94  LIST_ENTRY* le;
95 
96  Status = remove_free_space_inode(Vcb, fsi->key.obj_id, batchlist, Irp, &rollback);
97 
98  if (!NT_SUCCESS(Status))
99  ERR("remove_free_space_inode for (%llx,%x,%llx) returned %08x\n", fsi->key.obj_id, fsi->key.obj_type, fsi->key.offset, Status);
100 
101  le = Vcb->chunks.Flink;
102  while (le != &Vcb->chunks) {
104 
105  if (c->offset == tp.item->key.offset && c->cache) {
106  reap_fcb(c->cache);
107  c->cache = NULL;
108  }
109 
110  le = le->Flink;
111  }
112  }
113  } else
114  WARN("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
115  }
116 
117  b = find_next_item(Vcb, &tp, &next_tp, FALSE, Irp);
118  if (b)
119  tp = next_tp;
120  } while (b);
121 
123 
124  if (NT_SUCCESS(Status))
126  else
128 
129  if (Vcb->space_root) {
130  searchkey.obj_id = 0;
131  searchkey.obj_type = 0;
132  searchkey.offset = 0;
133 
134  Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, FALSE, Irp);
135  if (!NT_SUCCESS(Status)) {
136  ERR("find_item returned %08x\n", Status);
137  return Status;
138  }
139 
140  do {
142  if (!NT_SUCCESS(Status)) {
143  ERR("delete_tree_item returned %08x\n", Status);
144  return Status;
145  }
146 
147  b = find_next_item(Vcb, &tp, &next_tp, FALSE, Irp);
148  if (b)
149  tp = next_tp;
150  } while (b);
151  }
152 
153  // regenerate free space tree
154  if (Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE) {
155  LIST_ENTRY* le;
156 
157  ExAcquireResourceSharedLite(&Vcb->chunk_lock, TRUE);
158 
159  le = Vcb->chunks.Flink;
160  while (le != &Vcb->chunks) {
162 
163  if (!c->cache_loaded) {
165 
167  if (!NT_SUCCESS(Status)) {
168  ERR("load_cache_chunk(%llx) returned %08x\n", c->offset, Status);
170  ExReleaseResourceLite(&Vcb->chunk_lock);
171  return Status;
172  }
173 
174  c->changed = TRUE;
175  c->space_changed = TRUE;
176 
178  }
179 
180  le = le->Flink;
181  }
182 
183  ExReleaseResourceLite(&Vcb->chunk_lock);
184  }
185 
186  return Status;
187 }
188 
190  space* s;
191 
193 
194  if (!s) {
195  ERR("out of memory\n");
197  }
198 
199  s->address = offset;
200  s->size = size;
201 
202  if (IsListEmpty(list))
203  InsertTailList(list, &s->list_entry);
204  else {
206 
207  if (s2->address < offset)
208  InsertTailList(list, &s->list_entry);
209  else {
210  LIST_ENTRY* le;
211 
212  le = list->Flink;
213  while (le != list) {
215 
216  if (s2->address > offset) {
217  InsertTailList(le, &s->list_entry);
218  goto size;
219  }
220 
221  le = le->Flink;
222  }
223  }
224  }
225 
226 size:
227  if (!list_size)
228  return STATUS_SUCCESS;
229 
230  if (IsListEmpty(list_size))
231  InsertTailList(list_size, &s->list_entry_size);
232  else {
233  space* s2 = CONTAINING_RECORD(list_size->Blink, space, list_entry_size);
234 
235  if (s2->size >= size)
236  InsertTailList(list_size, &s->list_entry_size);
237  else {
238  LIST_ENTRY* le;
239 
240  le = list_size->Flink;
241  while (le != list_size) {
242  s2 = CONTAINING_RECORD(le, space, list_entry_size);
243 
244  if (s2->size <= size) {
245  InsertHeadList(le->Blink, &s->list_entry_size);
246  return STATUS_SUCCESS;
247  }
248 
249  le = le->Flink;
250  }
251  }
252  }
253 
254  return STATUS_SUCCESS;
255 }
256 
257 static void load_free_space_bitmap(device_extension* Vcb, chunk* c, UINT64 offset, void* data, UINT64* total_space) {
258  RTL_BITMAP bmph;
259  UINT32 i, *dwords = data;
260  ULONG runlength, index;
261 
262  // flip bits
263  for (i = 0; i < Vcb->superblock.sector_size / sizeof(UINT32); i++) {
264  dwords[i] = ~dwords[i];
265  }
266 
267  RtlInitializeBitMap(&bmph, data, Vcb->superblock.sector_size * 8);
268 
269  index = 0;
270  runlength = RtlFindFirstRunClear(&bmph, &index);
271 
272  while (runlength != 0) {
273  UINT64 addr, length;
274 
275  addr = offset + (index * Vcb->superblock.sector_size);
276  length = Vcb->superblock.sector_size * runlength;
277 
278  add_space_entry(&c->space, &c->space_size, addr, length);
279  index += runlength;
280  *total_space += length;
281 
282  runlength = RtlFindNextForwardRunClear(&bmph, index, &index);
283  }
284 }
285 
286 static void order_space_entry(space* s, LIST_ENTRY* list_size) {
287  LIST_ENTRY* le;
288 
289  if (IsListEmpty(list_size)) {
290  InsertHeadList(list_size, &s->list_entry_size);
291  return;
292  }
293 
294  le = list_size->Flink;
295 
296  while (le != list_size) {
297  space* s2 = CONTAINING_RECORD(le, space, list_entry_size);
298 
299  if (s2->size <= s->size) {
300  InsertHeadList(le->Blink, &s->list_entry_size);
301  return;
302  }
303 
304  le = le->Flink;
305  }
306 
307  InsertTailList(list_size, &s->list_entry_size);
308 }
309 
310 typedef struct {
314 
316  UINT64 i;
317 
318  for (i = 0; i < len; i++) {
319  LIST_ENTRY* le;
321  BOOL ignore = FALSE;
322 
323  le = stripes->Flink;
324  while (le != stripes) {
326 
327  if (ss->stripe == off + i) {
328  ignore = TRUE;
329  break;
330  }
331 
332  le = le->Flink;
333  }
334 
335  if (ignore)
336  continue;
337 
339  if (!ss) {
340  ERR("out of memory\n");
342  }
343 
344  ss->stripe = off + i;
345  InsertTailList(stripes, &ss->list_entry);
346  }
347 
348  return STATUS_SUCCESS;
349 }
350 
353  CHUNK_ITEM* ci = c->chunk_item;
354  CHUNK_ITEM_STRIPE* cis = (CHUNK_ITEM_STRIPE*)&ci[1];
355  UINT64 off_start, off_end, space = 0;
356  UINT16 i = 0, j;
357  LIST_ENTRY stripes;
358 
359  InitializeListHead(&stripes);
360 
361  while (superblock_addrs[i] != 0) {
362  if (ci->type & BLOCK_FLAG_RAID0 || ci->type & BLOCK_FLAG_RAID10) {
363  for (j = 0; j < ci->num_stripes; j++) {
364  ULONG sub_stripes = max(ci->sub_stripes, 1);
365 
366  if (cis[j].offset + (ci->size * ci->num_stripes / sub_stripes) > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
367  off_start = superblock_addrs[i] - cis[j].offset;
368  off_start -= off_start % ci->stripe_length;
369  off_start *= ci->num_stripes / sub_stripes;
370  off_start += (j / sub_stripes) * ci->stripe_length;
371 
372  off_end = off_start + ci->stripe_length;
373 
374  Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, 1);
375  if (!NT_SUCCESS(Status)) {
376  ERR("add_superblock_stripe returned %08x\n", Status);
377  goto end;
378  }
379  }
380  }
381  } else if (ci->type & BLOCK_FLAG_RAID5) {
382  for (j = 0; j < ci->num_stripes; j++) {
383  UINT64 stripe_size = ci->size / (ci->num_stripes - 1);
384 
385  if (cis[j].offset + stripe_size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
386  off_start = superblock_addrs[i] - cis[j].offset;
387  off_start -= off_start % (ci->stripe_length * (ci->num_stripes - 1));
388  off_start *= ci->num_stripes - 1;
389 
390  off_end = off_start + (ci->stripe_length * (ci->num_stripes - 1));
391 
392  Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length);
393  if (!NT_SUCCESS(Status)) {
394  ERR("add_superblock_stripe returned %08x\n", Status);
395  goto end;
396  }
397  }
398  }
399  } else if (ci->type & BLOCK_FLAG_RAID6) {
400  for (j = 0; j < ci->num_stripes; j++) {
401  UINT64 stripe_size = ci->size / (ci->num_stripes - 2);
402 
403  if (cis[j].offset + stripe_size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
404  off_start = superblock_addrs[i] - cis[j].offset;
405  off_start -= off_start % (ci->stripe_length * (ci->num_stripes - 2));
406  off_start *= ci->num_stripes - 2;
407 
408  off_end = off_start + (ci->stripe_length * (ci->num_stripes - 2));
409 
410  Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length);
411  if (!NT_SUCCESS(Status)) {
412  ERR("add_superblock_stripe returned %08x\n", Status);
413  goto end;
414  }
415  }
416  }
417  } else { // SINGLE, DUPLICATE, RAID1
418  for (j = 0; j < ci->num_stripes; j++) {
419  if (cis[j].offset + ci->size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
420  off_start = ((superblock_addrs[i] - cis[j].offset) / c->chunk_item->stripe_length) * c->chunk_item->stripe_length;
421  off_end = sector_align(superblock_addrs[i] - cis[j].offset + sizeof(superblock), c->chunk_item->stripe_length);
422 
423  Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length);
424  if (!NT_SUCCESS(Status)) {
425  ERR("add_superblock_stripe returned %08x\n", Status);
426  goto end;
427  }
428  }
429  }
430  }
431 
432  i++;
433  }
434 
436 
437 end:
438  while (!IsListEmpty(&stripes)) {
439  LIST_ENTRY* le = RemoveHeadList(&stripes);
441 
442  space++;
443 
444  ExFreePool(ss);
445  }
446 
447  if (NT_SUCCESS(Status))
448  *size = space * ci->stripe_length;
449 
450  return Status;
451 }
452 
454  KEY searchkey;
456  FREE_SPACE_ITEM* fsi;
458  UINT8* data;
460  UINT32 *checksums, crc32, i, num_sectors, num_valid_sectors, size;
461  FREE_SPACE_ENTRY* fse;
462  UINT64 num_entries, num_bitmaps, extent_length, bmpnum, off, total_space = 0, superblock_size;
463  LIST_ENTRY *le, rollback;
464 
465  // FIXME - does this break if Vcb->superblock.sector_size is not 4096?
466 
467  TRACE("(%p, %llx)\n", Vcb, c->offset);
468 
469  searchkey.obj_id = FREE_SPACE_CACHE_ID;
470  searchkey.obj_type = 0;
471  searchkey.offset = c->offset;
472 
473  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
474  if (!NT_SUCCESS(Status)) {
475  ERR("error - find_item returned %08x\n", Status);
476  return Status;
477  }
478 
479  if (keycmp(tp.item->key, searchkey)) {
480  TRACE("(%llx,%x,%llx) not found\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
481  return STATUS_NOT_FOUND;
482  }
483 
484  if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
485  WARN("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
486  return STATUS_NOT_FOUND;
487  }
488 
489  fsi = (FREE_SPACE_ITEM*)tp.item->data;
490 
491  if (fsi->key.obj_type != TYPE_INODE_ITEM) {
492  WARN("cache pointed to something other than an INODE_ITEM\n");
493  return STATUS_NOT_FOUND;
494  }
495 
496  inode = fsi->key.obj_id;
497  num_entries = fsi->num_entries;
498  num_bitmaps = fsi->num_bitmaps;
499 
500  Status = open_fcb(Vcb, Vcb->root_root, inode, BTRFS_TYPE_FILE, NULL, NULL, &c->cache, PagedPool, Irp);
501  if (!NT_SUCCESS(Status)) {
502  ERR("open_fcb returned %08x\n", Status);
503  return STATUS_NOT_FOUND;
504  }
505 
506  if (load_only)
507  return STATUS_SUCCESS;
508 
509  if (c->cache->inode_item.st_size == 0) {
510  WARN("cache had zero length\n");
511  free_fcb(c->cache);
512  c->cache = NULL;
513  return STATUS_NOT_FOUND;
514  }
515 
516  c->cache->inode_item.flags |= BTRFS_INODE_NODATACOW;
517 
518  if (num_entries == 0 && num_bitmaps == 0)
519  return STATUS_SUCCESS;
520 
521  size = (UINT32)sector_align(c->cache->inode_item.st_size, Vcb->superblock.sector_size);
522 
524 
525  if (!data) {
526  ERR("out of memory\n");
527  free_fcb(c->cache);
528  c->cache = NULL;
530  }
531 
532  if (c->chunk_item->size < 0x6400000) { // 100 MB
533  WARN("deleting free space cache for chunk smaller than 100MB\n");
534  goto clearcache;
535  }
536 
537  Status = read_file(c->cache, data, 0, c->cache->inode_item.st_size, NULL, NULL);
538  if (!NT_SUCCESS(Status)) {
539  ERR("read_file returned %08x\n", Status);
540  ExFreePool(data);
541 
542  c->cache->deleted = TRUE;
543  mark_fcb_dirty(c->cache);
544 
545  free_fcb(c->cache);
546  c->cache = NULL;
547  return STATUS_NOT_FOUND;
548  }
549 
550  if (size > c->cache->inode_item.st_size)
551  RtlZeroMemory(&data[c->cache->inode_item.st_size], (ULONG)(size - c->cache->inode_item.st_size));
552 
553  num_sectors = size / Vcb->superblock.sector_size;
554 
555  generation = (UINT64*)(data + (num_sectors * sizeof(UINT32)));
556 
557  if (*generation != fsi->generation) {
558  WARN("free space cache generation for %llx was %llx, expected %llx\n", c->offset, *generation, fsi->generation);
559  goto clearcache;
560  }
561 
562  extent_length = (num_sectors * sizeof(UINT32)) + sizeof(UINT64) + (num_entries * sizeof(FREE_SPACE_ENTRY));
563 
564  num_valid_sectors = (ULONG)((sector_align(extent_length, Vcb->superblock.sector_size) / Vcb->superblock.sector_size) + num_bitmaps);
565 
566  if (num_valid_sectors > num_sectors) {
567  ERR("free space cache for %llx was %llx sectors, expected at least %llx\n", c->offset, num_sectors, num_valid_sectors);
568  goto clearcache;
569  }
570 
571  checksums = (UINT32*)data;
572 
573  for (i = 0; i < num_valid_sectors; i++) {
574  if (i * Vcb->superblock.sector_size > sizeof(UINT32) * num_sectors)
575  crc32 = ~calc_crc32c(0xffffffff, &data[i * Vcb->superblock.sector_size], Vcb->superblock.sector_size);
576  else if ((i + 1) * Vcb->superblock.sector_size < sizeof(UINT32) * num_sectors)
577  crc32 = 0; // FIXME - test this
578  else
579  crc32 = ~calc_crc32c(0xffffffff, &data[sizeof(UINT32) * num_sectors], ((i + 1) * Vcb->superblock.sector_size) - (sizeof(UINT32) * num_sectors));
580 
581  if (crc32 != checksums[i]) {
582  WARN("checksum %llu was %08x, expected %08x\n", i, crc32, checksums[i]);
583  goto clearcache;
584  }
585  }
586 
587  off = (sizeof(UINT32) * num_sectors) + sizeof(UINT64);
588 
589  bmpnum = 0;
590  for (i = 0; i < num_entries; i++) {
591  if ((off + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size != off / Vcb->superblock.sector_size)
592  off = sector_align(off, Vcb->superblock.sector_size);
593 
594  fse = (FREE_SPACE_ENTRY*)&data[off];
595 
596  if (fse->type == FREE_SPACE_EXTENT) {
597  Status = add_space_entry(&c->space, &c->space_size, fse->offset, fse->size);
598  if (!NT_SUCCESS(Status)) {
599  ERR("add_space_entry returned %08x\n", Status);
600  ExFreePool(data);
601  return Status;
602  }
603 
604  total_space += fse->size;
605  } else if (fse->type != FREE_SPACE_BITMAP) {
606  ERR("unknown free-space type %x\n", fse->type);
607  }
608 
609  off += sizeof(FREE_SPACE_ENTRY);
610  }
611 
612  if (num_bitmaps > 0) {
613  bmpnum = sector_align(off, Vcb->superblock.sector_size) / Vcb->superblock.sector_size;
614  off = (sizeof(UINT32) * num_sectors) + sizeof(UINT64);
615 
616  for (i = 0; i < num_entries; i++) {
617  if ((off + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size != off / Vcb->superblock.sector_size)
618  off = sector_align(off, Vcb->superblock.sector_size);
619 
620  fse = (FREE_SPACE_ENTRY*)&data[off];
621 
622  if (fse->type == FREE_SPACE_BITMAP) {
623  // FIXME - make sure we don't overflow the buffer here
624  load_free_space_bitmap(Vcb, c, fse->offset, &data[bmpnum * Vcb->superblock.sector_size], &total_space);
625  bmpnum++;
626  }
627 
628  off += sizeof(FREE_SPACE_ENTRY);
629  }
630  }
631 
632  // do sanity check
633 
634  Status = get_superblock_size(c, &superblock_size);
635  if (!NT_SUCCESS(Status)) {
636  ERR("get_superblock_size returned %08x\n", Status);
637  ExFreePool(data);
638  return Status;
639  }
640 
641  if (c->chunk_item->size - c->used != total_space + superblock_size) {
642  WARN("invalidating cache for chunk %llx: space was %llx, expected %llx\n", c->offset, total_space + superblock_size, c->chunk_item->size - c->used);
643  goto clearcache;
644  }
645 
646  le = c->space.Flink;
647  while (le != &c->space) {
649  LIST_ENTRY* le2 = le->Flink;
650 
651  if (le2 != &c->space) {
653 
654  if (s2->address == s->address + s->size) {
655  s->size += s2->size;
656 
657  RemoveEntryList(&s2->list_entry);
658  RemoveEntryList(&s2->list_entry_size);
659  ExFreePool(s2);
660 
661  RemoveEntryList(&s->list_entry_size);
662  order_space_entry(s, &c->space_size);
663 
664  le2 = le;
665  }
666  }
667 
668  le = le2;
669  }
670 
671  ExFreePool(data);
672 
673  return STATUS_SUCCESS;
674 
675 clearcache:
676  ExFreePool(data);
677 
679 
681  if (!NT_SUCCESS(Status)) {
682  ERR("delete_tree_item returned %08x\n", Status);
683  return Status;
684  }
685 
686  Status = excise_extents(Vcb, c->cache, 0, c->cache->inode_item.st_size, Irp, &rollback);
687  if (!NT_SUCCESS(Status)) {
688  ERR("excise_extents returned %08x\n", Status);
690  return Status;
691  }
692 
694 
695  c->cache->deleted = TRUE;
696  mark_fcb_dirty(c->cache);
697 
698  c->old_cache = c->cache;
699  c->cache = NULL;
700 
701  le = c->space.Flink;
702  while (le != &c->space) {
704  LIST_ENTRY* le2 = le->Flink;
705 
706  RemoveEntryList(&s->list_entry);
707  RemoveEntryList(&s->list_entry_size);
708  ExFreePool(s);
709 
710  le = le2;
711  }
712 
713  return STATUS_NOT_FOUND;
714 }
715 
717  KEY searchkey;
718  traverse_ptr tp, next_tp;
720  ULONG* bmparr = NULL;
721  ULONG bmplen = 0;
722  LIST_ENTRY* le;
723 
724  TRACE("(%p, %llx)\n", Vcb, c->offset);
725 
726  if (!Vcb->space_root)
727  return STATUS_NOT_FOUND;
728 
729  searchkey.obj_id = c->offset;
730  searchkey.obj_type = TYPE_FREE_SPACE_INFO;
731  searchkey.offset = c->chunk_item->size;
732 
733  Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, FALSE, Irp);
734  if (!NT_SUCCESS(Status)) {
735  ERR("find_item returned %08x\n", Status);
736  return Status;
737  }
738 
739  if (keycmp(tp.item->key, searchkey)) {
740  TRACE("(%llx,%x,%llx) not found\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
741  return STATUS_NOT_FOUND;
742  }
743 
744  if (tp.item->size < sizeof(FREE_SPACE_INFO)) {
745  WARN("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_INFO));
746  return STATUS_NOT_FOUND;
747  }
748 
749  while (find_next_item(Vcb, &tp, &next_tp, FALSE, Irp)) {
750  tp = next_tp;
751 
752  if (tp.item->key.obj_id >= c->offset + c->chunk_item->size)
753  break;
754 
756  Status = add_space_entry(&c->space, &c->space_size, tp.item->key.obj_id, tp.item->key.offset);
757  if (!NT_SUCCESS(Status)) {
758  ERR("add_space_entry returned %08x\n", Status);
759  if (bmparr) ExFreePool(bmparr);
760  return Status;
761  }
762  } else if (tp.item->key.obj_type == TYPE_FREE_SPACE_BITMAP) {
763  ULONG explen, index, runlength;
764  RTL_BITMAP bmp;
765  UINT64 lastoff;
766 
767  explen = (ULONG)(tp.item->key.offset / (Vcb->superblock.sector_size * 8));
768 
769  if (tp.item->size < explen) {
770  WARN("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, explen);
771  return STATUS_NOT_FOUND;
772  } else if (tp.item->size == 0) {
773  WARN("(%llx,%x,%llx) has size of 0\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
774  return STATUS_NOT_FOUND;
775  }
776 
777  if (bmplen < tp.item->size) {
778  if (bmparr)
779  ExFreePool(bmparr);
780 
781  bmplen = (ULONG)sector_align(tp.item->size, sizeof(ULONG));
782  bmparr = ExAllocatePoolWithTag(PagedPool, bmplen, ALLOC_TAG);
783  if (!bmparr) {
784  ERR("out of memory\n");
786  }
787  }
788 
789  // We copy the bitmap because it supposedly has to be ULONG-aligned
790  RtlCopyMemory(bmparr, tp.item->data, tp.item->size);
791 
792  RtlInitializeBitMap(&bmp, bmparr, (ULONG)(tp.item->key.offset / Vcb->superblock.sector_size));
793 
794  lastoff = tp.item->key.obj_id;
795 
796  runlength = RtlFindFirstRunClear(&bmp, &index);
797 
798  while (runlength != 0) {
799  UINT64 runstart = tp.item->key.obj_id + (index * Vcb->superblock.sector_size);
800  UINT64 runend = runstart + (runlength * Vcb->superblock.sector_size);
801 
802  if (runstart > lastoff) {
803  Status = add_space_entry(&c->space, &c->space_size, lastoff, runstart - lastoff);
804  if (!NT_SUCCESS(Status)) {
805  ERR("add_space_entry returned %08x\n", Status);
806  if (bmparr) ExFreePool(bmparr);
807  return Status;
808  }
809  }
810 
811  lastoff = runend;
812 
813  runlength = RtlFindNextForwardRunClear(&bmp, index + runlength, &index);
814  }
815 
816  if (lastoff < tp.item->key.obj_id + tp.item->key.offset) {
817  Status = add_space_entry(&c->space, &c->space_size, lastoff, tp.item->key.obj_id + tp.item->key.offset - lastoff);
818  if (!NT_SUCCESS(Status)) {
819  ERR("add_space_entry returned %08x\n", Status);
820  if (bmparr) ExFreePool(bmparr);
821  return Status;
822  }
823  }
824  }
825  }
826 
827  if (bmparr)
828  ExFreePool(bmparr);
829 
830  le = c->space.Flink;
831  while (le != &c->space) {
833  LIST_ENTRY* le2 = le->Flink;
834 
835  if (le2 != &c->space) {
837 
838  if (s2->address == s->address + s->size) {
839  s->size += s2->size;
840 
841  RemoveEntryList(&s2->list_entry);
842  RemoveEntryList(&s2->list_entry_size);
843  ExFreePool(s2);
844 
845  RemoveEntryList(&s->list_entry_size);
846  order_space_entry(s, &c->space_size);
847 
848  le2 = le;
849  }
850  }
851 
852  le = le2;
853  }
854 
855  return STATUS_SUCCESS;
856 }
857 
859  traverse_ptr tp, next_tp;
860  KEY searchkey;
861  UINT64 lastaddr;
862  BOOL b;
863  space* s;
865 
866  if (Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE && Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID) {
868 
870  ERR("load_stored_free_space_tree returned %08x\n", Status);
871  return Status;
872  }
873  } else if (Vcb->superblock.generation - 1 == Vcb->superblock.cache_generation) {
875 
877  ERR("load_stored_free_space_cache returned %08x\n", Status);
878  return Status;
879  }
880  } else
882 
883  if (Status == STATUS_NOT_FOUND) {
884  TRACE("generating free space cache for chunk %llx\n", c->offset);
885 
886  searchkey.obj_id = c->offset;
887  searchkey.obj_type = TYPE_EXTENT_ITEM;
888  searchkey.offset = 0;
889 
890  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
891  if (!NT_SUCCESS(Status)) {
892  ERR("error - find_item returned %08x\n", Status);
893  return Status;
894  }
895 
896  lastaddr = c->offset;
897 
898  do {
899  if (tp.item->key.obj_id >= c->offset + c->chunk_item->size)
900  break;
901 
902  if (tp.item->key.obj_id >= c->offset && (tp.item->key.obj_type == TYPE_EXTENT_ITEM || tp.item->key.obj_type == TYPE_METADATA_ITEM)) {
903  if (tp.item->key.obj_id > lastaddr) {
905 
906  if (!s) {
907  ERR("out of memory\n");
909  }
910 
911  s->address = lastaddr;
912  s->size = tp.item->key.obj_id - lastaddr;
913  InsertTailList(&c->space, &s->list_entry);
914 
915  order_space_entry(s, &c->space_size);
916 
917  TRACE("(%llx,%llx)\n", s->address, s->size);
918  }
919 
921  lastaddr = tp.item->key.obj_id + Vcb->superblock.node_size;
922  else
923  lastaddr = tp.item->key.obj_id + tp.item->key.offset;
924  }
925 
926  b = find_next_item(Vcb, &tp, &next_tp, FALSE, Irp);
927  if (b)
928  tp = next_tp;
929  } while (b);
930 
931  if (lastaddr < c->offset + c->chunk_item->size) {
933 
934  if (!s) {
935  ERR("out of memory\n");
937  }
938 
939  s->address = lastaddr;
940  s->size = c->offset + c->chunk_item->size - lastaddr;
941  InsertTailList(&c->space, &s->list_entry);
942 
943  order_space_entry(s, &c->space_size);
944 
945  TRACE("(%llx,%llx)\n", s->address, s->size);
946  }
947  }
948 
949  return STATUS_SUCCESS;
950 }
951 
954 
955  if (c->cache_loaded)
956  return STATUS_SUCCESS;
957 
959  if (!NT_SUCCESS(Status)) {
960  ERR("load_free_space_cache returned %08x\n", Status);
961  return Status;
962  }
963 
965 
966  c->cache_loaded = TRUE;
967 
968  return STATUS_SUCCESS;
969 }
970 
973  LIST_ENTRY* le = fcb->Vcb->chunks.Flink;
974  chunk* c;
975  UINT64 flags;
976 
977  flags = fcb->Vcb->data_flags;
978 
979  while (le != &fcb->Vcb->chunks) {
981 
982  if (!c->readonly && !c->reloc) {
984 
985  if (c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= length) {
986  if (insert_extent_chunk(fcb->Vcb, fcb, c, start, length, FALSE, NULL, NULL, rollback, BTRFS_COMPRESSION_NONE, length, FALSE, 0))
987  return STATUS_SUCCESS;
988  }
989 
991  }
992 
993  le = le->Flink;
994  }
995 
997 
998  if (!NT_SUCCESS(Status)) {
999  ERR("alloc_chunk returned %08x\n", Status);
1000  return Status;
1001  }
1002 
1004 
1005  if (c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= length) {
1006  if (insert_extent_chunk(fcb->Vcb, fcb, c, start, length, FALSE, NULL, NULL, rollback, BTRFS_COMPRESSION_NONE, length, FALSE, 0))
1007  return STATUS_SUCCESS;
1008  }
1009 
1011 
1012  return STATUS_DISK_FULL;
1013 }
1014 
1016  LIST_ENTRY* le;
1017  NTSTATUS Status;
1018  UINT64 num_entries, new_cache_size, i;
1019  UINT32 num_sectors;
1020  BOOL realloc_extents = FALSE;
1021 
1022  // FIXME - also do bitmaps
1023  // FIXME - make sure this works when sector_size is not 4096
1024 
1025  *changed = FALSE;
1026 
1027  num_entries = 0;
1028 
1029  // num_entries is the number of entries in c->space and c->deleting - it might
1030  // be slightly higher then what we end up writing, but doing it this way is much
1031  // quicker and simpler.
1032  if (!IsListEmpty(&c->space)) {
1033  le = c->space.Flink;
1034  while (le != &c->space) {
1035  num_entries++;
1036 
1037  le = le->Flink;
1038  }
1039  }
1040 
1041  if (!IsListEmpty(&c->deleting)) {
1042  le = c->deleting.Flink;
1043  while (le != &c->deleting) {
1044  num_entries++;
1045 
1046  le = le->Flink;
1047  }
1048  }
1049 
1050  new_cache_size = sizeof(UINT64) + (num_entries * sizeof(FREE_SPACE_ENTRY));
1051 
1052  num_sectors = (UINT32)sector_align(new_cache_size, Vcb->superblock.sector_size) / Vcb->superblock.sector_size;
1053  num_sectors = (UINT32)sector_align(num_sectors, CACHE_INCREMENTS);
1054 
1055  // adjust for padding
1056  // FIXME - there must be a more efficient way of doing this
1057  new_cache_size = sizeof(UINT64) + (sizeof(UINT32) * num_sectors);
1058  for (i = 0; i < num_entries; i++) {
1059  if ((new_cache_size / Vcb->superblock.sector_size) != ((new_cache_size + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size))
1060  new_cache_size = sector_align(new_cache_size, Vcb->superblock.sector_size);
1061 
1062  new_cache_size += sizeof(FREE_SPACE_ENTRY);
1063  }
1064 
1065  new_cache_size = sector_align(new_cache_size, CACHE_INCREMENTS * Vcb->superblock.sector_size);
1066 
1067  TRACE("chunk %llx: cache_size = %llx, new_cache_size = %llx\n", c->offset, c->cache ? c->cache->inode_item.st_size : 0, new_cache_size);
1068 
1069  if (c->cache) {
1070  if (new_cache_size > c->cache->inode_item.st_size)
1071  realloc_extents = TRUE;
1072  else {
1073  le = c->cache->extents.Flink;
1074 
1075  while (le != &c->cache->extents) {
1077 
1078  if (!ext->ignore && (ext->extent_data.type == EXTENT_TYPE_REGULAR || ext->extent_data.type == EXTENT_TYPE_PREALLOC)) {
1079  EXTENT_DATA2* ed2 = (EXTENT_DATA2*)&ext->extent_data.data[0];
1080 
1081  if (ed2->size != 0) {
1083 
1084  if (c2 && (c2->readonly || c2->reloc)) {
1085  realloc_extents = TRUE;
1086  break;
1087  }
1088  }
1089  }
1090 
1091  le = le->Flink;
1092  }
1093  }
1094  }
1095 
1096  if (!c->cache) {
1097  FREE_SPACE_ITEM* fsi;
1098  KEY searchkey;
1099  traverse_ptr tp;
1100 
1101  // create new inode
1102 
1103  c->cache = create_fcb(Vcb, PagedPool);
1104  if (!c->cache) {
1105  ERR("out of memory\n");
1107  }
1108 
1109  c->cache->Vcb = Vcb;
1110 
1111  c->cache->inode_item.st_size = new_cache_size;
1112  c->cache->inode_item.st_blocks = new_cache_size;
1113  c->cache->inode_item.st_nlink = 1;
1114  c->cache->inode_item.st_mode = S_IRUSR | S_IWUSR | __S_IFREG;
1116 
1117  c->cache->Header.IsFastIoPossible = fast_io_possible(c->cache);
1118  c->cache->Header.AllocationSize.QuadPart = 0;
1119  c->cache->Header.FileSize.QuadPart = 0;
1120  c->cache->Header.ValidDataLength.QuadPart = 0;
1121 
1122  c->cache->subvol = Vcb->root_root;
1123 
1124  c->cache->inode = InterlockedIncrement64(&Vcb->root_root->lastinode);
1125 
1126  c->cache->type = BTRFS_TYPE_FILE;
1127  c->cache->created = TRUE;
1128 
1129  // create new free space entry
1130 
1132  if (!fsi) {
1133  ERR("out of memory\n");
1134  reap_fcb(c->cache);
1135  c->cache = NULL;
1137  }
1138 
1139  searchkey.obj_id = FREE_SPACE_CACHE_ID;
1140  searchkey.obj_type = 0;
1141  searchkey.offset = c->offset;
1142 
1143  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
1144  if (!NT_SUCCESS(Status)) {
1145  ERR("error - find_item returned %08x\n", Status);
1146  ExFreePool(fsi);
1147  reap_fcb(c->cache);
1148  c->cache = NULL;
1149  return Status;
1150  }
1151 
1152  if (!keycmp(searchkey, tp.item->key)) {
1154  if (!NT_SUCCESS(Status)) {
1155  ERR("delete_tree_item returned %08x\n", Status);
1156  ExFreePool(fsi);
1157  reap_fcb(c->cache);
1158  c->cache = NULL;
1159  return Status;
1160  }
1161  }
1162 
1163  fsi->key.obj_id = c->cache->inode;
1164  fsi->key.obj_type = TYPE_INODE_ITEM;
1165  fsi->key.offset = 0;
1166 
1167  Status = insert_tree_item(Vcb, Vcb->root_root, FREE_SPACE_CACHE_ID, 0, c->offset, fsi, sizeof(FREE_SPACE_ITEM), NULL, Irp);
1168  if (!NT_SUCCESS(Status)) {
1169  ERR("insert_tree_item returned %08x\n", Status);
1170  ExFreePool(fsi);
1171  reap_fcb(c->cache);
1172  c->cache = NULL;
1173  return Status;
1174  }
1175 
1176  // allocate space
1177 
1178  Status = insert_cache_extent(c->cache, 0, new_cache_size, rollback);
1179  if (!NT_SUCCESS(Status)) {
1180  ERR("insert_cache_extent returned %08x\n", Status);
1181  reap_fcb(c->cache);
1182  c->cache = NULL;
1183  return Status;
1184  }
1185 
1186  c->cache->extents_changed = TRUE;
1187  InsertTailList(&Vcb->all_fcbs, &c->cache->list_entry_all);
1188 
1189  Status = flush_fcb(c->cache, TRUE, batchlist, Irp);
1190  if (!NT_SUCCESS(Status)) {
1191  ERR("flush_fcb returned %08x\n", Status);
1192  free_fcb(c->cache);
1193  c->cache = NULL;
1194  return Status;
1195  }
1196 
1197  *changed = TRUE;
1198  } else if (realloc_extents) {
1199  KEY searchkey;
1200  traverse_ptr tp;
1201 
1202  TRACE("reallocating extents\n");
1203 
1204  // add free_space entry to tree cache
1205 
1206  searchkey.obj_id = FREE_SPACE_CACHE_ID;
1207  searchkey.obj_type = 0;
1208  searchkey.offset = c->offset;
1209 
1210  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
1211  if (!NT_SUCCESS(Status)) {
1212  ERR("error - find_item returned %08x\n", Status);
1213  return Status;
1214  }
1215 
1216  if (keycmp(searchkey, tp.item->key)) {
1217  ERR("could not find (%llx,%x,%llx) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1218  return STATUS_INTERNAL_ERROR;
1219  }
1220 
1221  if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
1222  ERR("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
1223  return STATUS_INTERNAL_ERROR;
1224  }
1225 
1226  tp.tree->write = TRUE;
1227 
1228  // remove existing extents
1229 
1230  if (c->cache->inode_item.st_size > 0) {
1231  le = c->cache->extents.Flink;
1232 
1233  while (le != &c->cache->extents) {
1235 
1236  if (!ext->ignore && (ext->extent_data.type == EXTENT_TYPE_REGULAR || ext->extent_data.type == EXTENT_TYPE_PREALLOC)) {
1237  EXTENT_DATA2* ed2 = (EXTENT_DATA2*)&ext->extent_data.data[0];
1238 
1239  if (ed2->size != 0) {
1241 
1242  if (c2) {
1243  c2->changed = TRUE;
1244  c2->space_changed = TRUE;
1245  }
1246  }
1247  }
1248 
1249  le = le->Flink;
1250  }
1251 
1252  Status = excise_extents(Vcb, c->cache, 0, c->cache->inode_item.st_size, Irp, rollback);
1253  if (!NT_SUCCESS(Status)) {
1254  ERR("excise_extents returned %08x\n", Status);
1255  return Status;
1256  }
1257  }
1258 
1259  // add new extent
1260 
1261  Status = insert_cache_extent(c->cache, 0, new_cache_size, rollback);
1262  if (!NT_SUCCESS(Status)) {
1263  ERR("insert_cache_extent returned %08x\n", Status);
1264  return Status;
1265  }
1266 
1267  // modify INODE_ITEM
1268 
1269  c->cache->inode_item.st_size = new_cache_size;
1270  c->cache->inode_item.st_blocks = new_cache_size;
1271 
1272  Status = flush_fcb(c->cache, TRUE, batchlist, Irp);
1273  if (!NT_SUCCESS(Status)) {
1274  ERR("flush_fcb returned %08x\n", Status);
1275  return Status;
1276  }
1277 
1278  *changed = TRUE;
1279  } else {
1280  KEY searchkey;
1281  traverse_ptr tp;
1282 
1283  // add INODE_ITEM and free_space entry to tree cache, for writing later
1284 
1285  searchkey.obj_id = c->cache->inode;
1286  searchkey.obj_type = TYPE_INODE_ITEM;
1287  searchkey.offset = 0;
1288 
1289  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
1290  if (!NT_SUCCESS(Status)) {
1291  ERR("error - find_item returned %08x\n", Status);
1292  return Status;
1293  }
1294 
1295  if (keycmp(searchkey, tp.item->key)) {
1296  INODE_ITEM* ii;
1297 
1299  if (!ii) {
1300  ERR("out of memory\n");
1302  }
1303 
1304  RtlCopyMemory(ii, &c->cache->inode_item, sizeof(INODE_ITEM));
1305 
1306  Status = insert_tree_item(Vcb, Vcb->root_root, c->cache->inode, TYPE_INODE_ITEM, 0, ii, sizeof(INODE_ITEM), NULL, Irp);
1307  if (!NT_SUCCESS(Status)) {
1308  ERR("insert_tree_item returned %08x\n", Status);
1309  ExFreePool(ii);
1310  return Status;
1311  }
1312 
1313  *changed = TRUE;
1314  } else {
1315  if (tp.item->size < sizeof(INODE_ITEM)) {
1316  ERR("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(INODE_ITEM));
1317  return STATUS_INTERNAL_ERROR;
1318  }
1319 
1320  tp.tree->write = TRUE;
1321  }
1322 
1323  searchkey.obj_id = FREE_SPACE_CACHE_ID;
1324  searchkey.obj_type = 0;
1325  searchkey.offset = c->offset;
1326 
1327  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
1328  if (!NT_SUCCESS(Status)) {
1329  ERR("error - find_item returned %08x\n", Status);
1330  return Status;
1331  }
1332 
1333  if (keycmp(searchkey, tp.item->key)) {
1334  ERR("could not find (%llx,%x,%llx) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1335  return STATUS_INTERNAL_ERROR;
1336  }
1337 
1338  if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
1339  ERR("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
1340  return STATUS_INTERNAL_ERROR;
1341  }
1342 
1343  tp.tree->write = TRUE;
1344  }
1345 
1346  // FIXME - reduce inode allocation if cache is shrinking. Make sure to avoid infinite write loops
1347 
1348  return STATUS_SUCCESS;
1349 }
1350 
1352  LIST_ENTRY *le, batchlist;
1353  NTSTATUS Status;
1354 
1355  *changed = FALSE;
1356 
1357  InitializeListHead(&batchlist);
1358 
1359  ExAcquireResourceExclusiveLite(&Vcb->chunk_lock, TRUE);
1360 
1361  le = Vcb->chunks.Flink;
1362  while (le != &Vcb->chunks) {
1364 
1365  if (c->space_changed && c->chunk_item->size >= 0x6400000) { // 100MB
1366  BOOL b;
1367 
1369  Status = allocate_cache_chunk(Vcb, c, &b, &batchlist, Irp, rollback);
1371 
1372  if (b)
1373  *changed = TRUE;
1374 
1375  if (!NT_SUCCESS(Status)) {
1376  ERR("allocate_cache_chunk(%llx) returned %08x\n", c->offset, Status);
1377  ExReleaseResourceLite(&Vcb->chunk_lock);
1378  clear_batch_list(Vcb, &batchlist);
1379  return Status;
1380  }
1381  }
1382 
1383  le = le->Flink;
1384  }
1385 
1386  ExReleaseResourceLite(&Vcb->chunk_lock);
1387 
1388  Status = commit_batch_list(Vcb, &batchlist, Irp);
1389  if (!NT_SUCCESS(Status)) {
1390  ERR("commit_batch_list returned %08x\n", Status);
1391  return Status;
1392  }
1393 
1394  return STATUS_SUCCESS;
1395 }
1396 
1398  rollback_space* rs;
1399 
1401  if (!rs) {
1402  ERR("out of memory\n");
1403  return;
1404  }
1405 
1406  rs->list = list;
1407  rs->list_size = list_size;
1408  rs->address = address;
1409  rs->length = length;
1410  rs->chunk = c;
1411 
1413 }
1414 
1416  LIST_ENTRY* le;
1417  space *s, *s2;
1418 
1419  if (IsListEmpty(list)) {
1421 
1422  if (!s) {
1423  ERR("out of memory\n");
1424  return;
1425  }
1426 
1427  s->address = address;
1428  s->size = length;
1429  InsertTailList(list, &s->list_entry);
1430 
1431  if (list_size)
1432  InsertTailList(list_size, &s->list_entry_size);
1433 
1434  if (rollback)
1435  add_rollback_space(rollback, TRUE, list, list_size, address, length, c);
1436 
1437  return;
1438  }
1439 
1440  le = list->Flink;
1441  do {
1443 
1444  // old entry envelops new one completely
1445  if (s2->address <= address && s2->address + s2->size >= address + length)
1446  return;
1447 
1448  // new entry envelops old one completely
1449  if (address <= s2->address && address + length >= s2->address + s2->size) {
1450  if (address < s2->address) {
1451  if (rollback)
1452  add_rollback_space(rollback, TRUE, list, list_size, address, s2->address - address, c);
1453 
1454  s2->size += s2->address - address;
1455  s2->address = address;
1456 
1457  while (s2->list_entry.Blink != list) {
1458  space* s3 = CONTAINING_RECORD(s2->list_entry.Blink, space, list_entry);
1459 
1460  if (s3->address + s3->size == s2->address) {
1461  s2->address = s3->address;
1462  s2->size += s3->size;
1463 
1465 
1466  if (list_size)
1468 
1469  ExFreePool(s3);
1470  } else
1471  break;
1472  }
1473  }
1474 
1475  if (length > s2->size) {
1476  if (rollback)
1477  add_rollback_space(rollback, TRUE, list, list_size, s2->address + s2->size, address + length - s2->address - s2->size, c);
1478 
1479  s2->size = length;
1480 
1481  while (s2->list_entry.Flink != list) {
1482  space* s3 = CONTAINING_RECORD(s2->list_entry.Flink, space, list_entry);
1483 
1484  if (s3->address <= s2->address + s2->size) {
1485  s2->size = max(s2->size, s3->address + s3->size - s2->address);
1486 
1488 
1489  if (list_size)
1491 
1492  ExFreePool(s3);
1493  } else
1494  break;
1495  }
1496  }
1497 
1498  if (list_size) {
1499  RemoveEntryList(&s2->list_entry_size);
1500  order_space_entry(s2, list_size);
1501  }
1502 
1503  return;
1504  }
1505 
1506  // new entry overlaps start of old one
1507  if (address < s2->address && address + length >= s2->address) {
1508  if (rollback)
1509  add_rollback_space(rollback, TRUE, list, list_size, address, s2->address - address, c);
1510 
1511  s2->size += s2->address - address;
1512  s2->address = address;
1513 
1514  while (s2->list_entry.Blink != list) {
1515  space* s3 = CONTAINING_RECORD(s2->list_entry.Blink, space, list_entry);
1516 
1517  if (s3->address + s3->size == s2->address) {
1518  s2->address = s3->address;
1519  s2->size += s3->size;
1520 
1522 
1523  if (list_size)
1525 
1526  ExFreePool(s3);
1527  } else
1528  break;
1529  }
1530 
1531  if (list_size) {
1532  RemoveEntryList(&s2->list_entry_size);
1533  order_space_entry(s2, list_size);
1534  }
1535 
1536  return;
1537  }
1538 
1539  // new entry overlaps end of old one
1540  if (address <= s2->address + s2->size && address + length > s2->address + s2->size) {
1541  if (rollback)
1542  add_rollback_space(rollback, TRUE, list, list_size, address, s2->address + s2->size - address, c);
1543 
1544  s2->size = address + length - s2->address;
1545 
1546  while (s2->list_entry.Flink != list) {
1547  space* s3 = CONTAINING_RECORD(s2->list_entry.Flink, space, list_entry);
1548 
1549  if (s3->address <= s2->address + s2->size) {
1550  s2->size = max(s2->size, s3->address + s3->size - s2->address);
1551 
1553 
1554  if (list_size)
1556 
1557  ExFreePool(s3);
1558  } else
1559  break;
1560  }
1561 
1562  if (list_size) {
1563  RemoveEntryList(&s2->list_entry_size);
1564  order_space_entry(s2, list_size);
1565  }
1566 
1567  return;
1568  }
1569 
1570  // add completely separate entry
1571  if (s2->address > address + length) {
1573 
1574  if (!s) {
1575  ERR("out of memory\n");
1576  return;
1577  }
1578 
1579  if (rollback)
1580  add_rollback_space(rollback, TRUE, list, list_size, address, length, c);
1581 
1582  s->address = address;
1583  s->size = length;
1584  InsertHeadList(s2->list_entry.Blink, &s->list_entry);
1585 
1586  if (list_size)
1587  order_space_entry(s, list_size);
1588 
1589  return;
1590  }
1591 
1592  le = le->Flink;
1593  } while (le != list);
1594 
1595  // check if contiguous with last entry
1596  if (s2->address + s2->size == address) {
1597  s2->size += length;
1598 
1599  if (list_size) {
1600  RemoveEntryList(&s2->list_entry_size);
1601  order_space_entry(s2, list_size);
1602  }
1603 
1604  return;
1605  }
1606 
1607  // otherwise, insert at end
1609 
1610  if (!s) {
1611  ERR("out of memory\n");
1612  return;
1613  }
1614 
1615  s->address = address;
1616  s->size = length;
1617  InsertTailList(list, &s->list_entry);
1618 
1619  if (list_size)
1620  order_space_entry(s, list_size);
1621 
1622  if (rollback)
1623  add_rollback_space(rollback, TRUE, list, list_size, address, length, c);
1624 }
1625 
1626 static void space_list_merge(LIST_ENTRY* spacelist, LIST_ENTRY* spacelist_size, LIST_ENTRY* deleting) {
1627  LIST_ENTRY* le;
1628 
1629  if (!IsListEmpty(deleting)) {
1630  le = deleting->Flink;
1631  while (le != deleting) {
1633 
1634  space_list_add2(spacelist, spacelist_size, s->address, s->size, NULL, NULL);
1635 
1636  le = le->Flink;
1637  }
1638  }
1639 }
1640 
1642  NTSTATUS Status;
1643  KEY searchkey;
1644  traverse_ptr tp;
1645  FREE_SPACE_ITEM* fsi;
1646  void* data;
1647  UINT64 num_entries, *cachegen, off;
1648  UINT32 *checksums, num_sectors, i;
1649  LIST_ENTRY* le;
1650 
1651  space_list_merge(&c->space, &c->space_size, &c->deleting);
1652 
1653  data = ExAllocatePoolWithTag(NonPagedPool, (ULONG)c->cache->inode_item.st_size, ALLOC_TAG);
1654  if (!data) {
1655  ERR("out of memory\n");
1657  }
1658 
1659  RtlZeroMemory(data, (ULONG)c->cache->inode_item.st_size);
1660 
1661  num_entries = 0;
1662  num_sectors = (UINT32)(c->cache->inode_item.st_size / Vcb->superblock.sector_size);
1663  off = (sizeof(UINT32) * num_sectors) + sizeof(UINT64);
1664 
1665  le = c->space.Flink;
1666  while (le != &c->space) {
1667  FREE_SPACE_ENTRY* fse;
1668 
1670 
1671  if ((off + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size != off / Vcb->superblock.sector_size)
1672  off = sector_align(off, Vcb->superblock.sector_size);
1673 
1674  fse = (FREE_SPACE_ENTRY*)((UINT8*)data + off);
1675 
1676  fse->offset = s->address;
1677  fse->size = s->size;
1678  fse->type = FREE_SPACE_EXTENT;
1679  num_entries++;
1680 
1681  off += sizeof(FREE_SPACE_ENTRY);
1682 
1683  le = le->Flink;
1684  }
1685 
1686  // update INODE_ITEM
1687 
1688  c->cache->inode_item.generation = Vcb->superblock.generation;
1689  c->cache->inode_item.transid = Vcb->superblock.generation;
1690  c->cache->inode_item.sequence++;
1691  c->cache->inode_item.st_ctime = *now;
1692 
1693  Status = flush_fcb(c->cache, TRUE, batchlist, Irp);
1694  if (!NT_SUCCESS(Status)) {
1695  ERR("flush_fcb returned %08x\n", Status);
1696  goto end;
1697  }
1698 
1699  // update free_space item
1700 
1701  searchkey.obj_id = FREE_SPACE_CACHE_ID;
1702  searchkey.obj_type = 0;
1703  searchkey.offset = c->offset;
1704 
1705  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
1706  if (!NT_SUCCESS(Status)) {
1707  ERR("error - find_item returned %08x\n", Status);
1708  goto end;
1709  }
1710 
1711  if (keycmp(searchkey, tp.item->key)) {
1712  ERR("could not find (%llx,%x,%llx) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1714  goto end;
1715  }
1716 
1717  if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
1718  ERR("(%llx,%x,%llx) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
1720  goto end;
1721  }
1722 
1723  fsi = (FREE_SPACE_ITEM*)tp.item->data;
1724 
1725  fsi->generation = Vcb->superblock.generation;
1726  fsi->num_entries = num_entries;
1727  fsi->num_bitmaps = 0;
1728 
1729  // set cache generation
1730 
1731  cachegen = (UINT64*)((UINT8*)data + (sizeof(UINT32) * num_sectors));
1732  *cachegen = Vcb->superblock.generation;
1733 
1734  // calculate cache checksums
1735 
1736  checksums = (UINT32*)data;
1737 
1738  // FIXME - if we know sector is fully zeroed, use cached checksum
1739 
1740  for (i = 0; i < num_sectors; i++) {
1741  if (i * Vcb->superblock.sector_size > sizeof(UINT32) * num_sectors)
1742  checksums[i] = ~calc_crc32c(0xffffffff, (UINT8*)data + (i * Vcb->superblock.sector_size), Vcb->superblock.sector_size);
1743  else if ((i + 1) * Vcb->superblock.sector_size < sizeof(UINT32) * num_sectors)
1744  checksums[i] = 0; // FIXME - test this
1745  else
1746  checksums[i] = ~calc_crc32c(0xffffffff, (UINT8*)data + (sizeof(UINT32) * num_sectors), ((i + 1) * Vcb->superblock.sector_size) - (sizeof(UINT32) * num_sectors));
1747  }
1748 
1749  // write cache
1750 
1751  Status = do_write_file(c->cache, 0, c->cache->inode_item.st_size, data, NULL, FALSE, 0, rollback);
1752  if (!NT_SUCCESS(Status)) {
1753  ERR("do_write_file returned %08x\n", Status);
1754 
1755  // Writing the cache isn't critical, so we don't return an error if writing fails. This means
1756  // we can still flush on a degraded mount if metadata is RAID1 but data is RAID0.
1757  }
1758 
1760 
1761 end:
1762  ExFreePool(data);
1763 
1764  return Status;
1765 }
1766 
1768  NTSTATUS Status;
1769  LIST_ENTRY* le;
1770  FREE_SPACE_INFO* fsi;
1771 
1773  if (!fsi) {
1774  ERR("out of memory\n");
1776  }
1777 
1778  space_list_merge(&c->space, &c->space_size, &c->deleting);
1779 
1780  fsi->count = 0;
1781  fsi->flags = 0;
1782 
1783  le = c->space.Flink;
1784  while (le != &c->space) {
1786 
1787  fsi->count++;
1788 
1789  Status = insert_tree_item_batch(batchlist, Vcb, Vcb->space_root, s->address, TYPE_FREE_SPACE_EXTENT, s->size,
1790  NULL, 0, Batch_Insert);
1791  if (!NT_SUCCESS(Status)) {
1792  ERR("insert_tree_item_batch returned %08x\n", Status);
1793  ExFreePool(fsi);
1794  return Status;
1795  }
1796 
1797  le = le->Flink;
1798  }
1799 
1800  Status = insert_tree_item_batch(batchlist, Vcb, Vcb->space_root, c->offset, TYPE_FREE_SPACE_INFO, c->chunk_item->size,
1802  if (!NT_SUCCESS(Status)) {
1803  ERR("insert_tree_item_batch returned %08x\n", Status);
1804  ExFreePool(fsi);
1805  return Status;
1806  }
1807 
1808  Status = insert_tree_item_batch(batchlist, Vcb, Vcb->space_root, c->offset, TYPE_FREE_SPACE_INFO, c->chunk_item->size,
1809  fsi, sizeof(FREE_SPACE_INFO), Batch_Insert);
1810  if (!NT_SUCCESS(Status)) {
1811  ERR("insert_tree_item_batch returned %08x\n", Status);
1812  ExFreePool(fsi);
1813  return Status;
1814  }
1815 
1816  return STATUS_SUCCESS;
1817 }
1818 
1820  LIST_ENTRY *le, batchlist;
1821  NTSTATUS Status;
1822  chunk* c;
1824  BTRFS_TIME now;
1825 
1828 
1829  InitializeListHead(&batchlist);
1830 
1831  le = Vcb->chunks.Flink;
1832  while (le != &Vcb->chunks) {
1834 
1835  if (c->space_changed && c->chunk_item->size >= 0x6400000) { // 100MB
1837  Status = update_chunk_cache(Vcb, c, &now, &batchlist, Irp, rollback);
1839 
1840  if (!NT_SUCCESS(Status)) {
1841  ERR("update_chunk_cache(%llx) returned %08x\n", c->offset, Status);
1842  clear_batch_list(Vcb, &batchlist);
1843  return Status;
1844  }
1845  }
1846 
1847  le = le->Flink;
1848  }
1849 
1850  Status = commit_batch_list(Vcb, &batchlist, Irp);
1851  if (!NT_SUCCESS(Status)) {
1852  ERR("commit_batch_list returned %08x\n", Status);
1853  return Status;
1854  }
1855 
1856  le = Vcb->chunks.Flink;
1857  while (le != &Vcb->chunks) {
1859 
1860  if (c->changed && (c->chunk_item->type & BLOCK_FLAG_RAID5 || c->chunk_item->type & BLOCK_FLAG_RAID6)) {
1861  ExAcquireResourceExclusiveLite(&c->partial_stripes_lock, TRUE);
1862 
1863  while (!IsListEmpty(&c->partial_stripes)) {
1865 
1866  Status = flush_partial_stripe(Vcb, c, ps);
1867 
1868  if (ps->bmparr)
1869  ExFreePool(ps->bmparr);
1870 
1871  ExFreePool(ps);
1872 
1873  if (!NT_SUCCESS(Status)) {
1874  ERR("flush_partial_stripe returned %08x\n", Status);
1875  ExReleaseResourceLite(&c->partial_stripes_lock);
1876  return Status;
1877  }
1878  }
1879 
1880  ExReleaseResourceLite(&c->partial_stripes_lock);
1881  }
1882 
1883  le = le->Flink;
1884  }
1885 
1886  return STATUS_SUCCESS;
1887 }
1888 
1890  LIST_ENTRY *le, batchlist;
1891  NTSTATUS Status;
1892  chunk* c;
1893 
1894  Vcb->superblock.compat_ro_flags |= BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID;
1895 
1896  InitializeListHead(&batchlist);
1897 
1898  ExAcquireResourceSharedLite(&Vcb->chunk_lock, TRUE);
1899 
1900  le = Vcb->chunks.Flink;
1901  while (le != &Vcb->chunks) {
1903 
1904  if (c->space_changed) {
1906  Status = update_chunk_cache_tree(Vcb, c, &batchlist);
1908 
1909  if (!NT_SUCCESS(Status)) {
1910  ERR("update_chunk_cache_tree(%llx) returned %08x\n", c->offset, Status);
1911  ExReleaseResourceLite(&Vcb->chunk_lock);
1912  clear_batch_list(Vcb, &batchlist);
1913  return Status;
1914  }
1915  }
1916 
1917  le = le->Flink;
1918  }
1919 
1920  ExReleaseResourceLite(&Vcb->chunk_lock);
1921 
1922  Status = commit_batch_list(Vcb, &batchlist, Irp);
1923  if (!NT_SUCCESS(Status)) {
1924  ERR("commit_batch_list returned %08x\n", Status);
1925  return Status;
1926  }
1927 
1928  return STATUS_SUCCESS;
1929 }
1930 
1932  TRACE("(%p, %llx, %llx, %p)\n", c, address, length, rollback);
1933 
1934  c->changed = TRUE;
1935  c->space_changed = TRUE;
1936 
1937  space_list_add2(&c->deleting, NULL, address, length, c, rollback);
1938 }
1939 
1941  LIST_ENTRY *le, *le2;
1942  space *s, *s2;
1943 
1944  if (IsListEmpty(list))
1945  return;
1946 
1947  le = list->Flink;
1948  while (le != list) {
1950  le2 = le->Flink;
1951 
1952  if (s2->address >= address + length)
1953  return;
1954 
1955  if (s2->address >= address && s2->address + s2->size <= address + length) { // remove entry entirely
1956  if (rollback)
1957  add_rollback_space(rollback, FALSE, list, list_size, s2->address, s2->size, c);
1958 
1959  RemoveEntryList(&s2->list_entry);
1960 
1961  if (list_size)
1962  RemoveEntryList(&s2->list_entry_size);
1963 
1964  ExFreePool(s2);
1965  } else if (address + length > s2->address && address + length < s2->address + s2->size) {
1966  if (address > s2->address) { // cut out hole
1967  if (rollback)
1969 
1971 
1972  if (!s) {
1973  ERR("out of memory\n");
1974  return;
1975  }
1976 
1977  s->address = s2->address;
1978  s->size = address - s2->address;
1979  InsertHeadList(s2->list_entry.Blink, &s->list_entry);
1980 
1981  s2->size = s2->address + s2->size - address - length;
1982  s2->address = address + length;
1983 
1984  if (list_size) {
1985  RemoveEntryList(&s2->list_entry_size);
1986  order_space_entry(s2, list_size);
1987  order_space_entry(s, list_size);
1988  }
1989 
1990  return;
1991  } else { // remove start of entry
1992  if (rollback)
1993  add_rollback_space(rollback, FALSE, list, list_size, s2->address, address + length - s2->address, c);
1994 
1995  s2->size -= address + length - s2->address;
1996  s2->address = address + length;
1997 
1998  if (list_size) {
1999  RemoveEntryList(&s2->list_entry_size);
2000  order_space_entry(s2, list_size);
2001  }
2002  }
2003  } else if (address > s2->address && address < s2->address + s2->size) { // remove end of entry
2004  if (rollback)
2005  add_rollback_space(rollback, FALSE, list, list_size, address, s2->address + s2->size - address, c);
2006 
2007  s2->size = address - s2->address;
2008 
2009  if (list_size) {
2010  RemoveEntryList(&s2->list_entry_size);
2011  order_space_entry(s2, list_size);
2012  }
2013  }
2014 
2015  le = le2;
2016  }
2017 }
2018 
2020  LIST_ENTRY* list;
2021 
2022  list = deleting ? &c->deleting : &c->space;
2023 
2024  c->changed = TRUE;
2025  c->space_changed = TRUE;
2026 
2027  space_list_subtract2(list, deleting ? NULL : &c->space_size, address, length, c, rollback);
2028 }
#define KeQuerySystemTime(t)
Definition: env_spec_w32.h:570
UINT32 count
Definition: btrfs.h:508
LIST_ENTRY * list_size
Definition: btrfs_drv.h:1220
int add
Definition: i386-dis.c:3122
ULONG * bmparr
Definition: btrfs_drv.h:519
static NTSTATUS insert_cache_extent(fcb *fcb, UINT64 start, UINT64 length, LIST_ENTRY *rollback)
Definition: free-space.c:971
void do_rollback(device_extension *Vcb, LIST_ENTRY *rollback)
Definition: treefuncs.c:1049
NTSTATUS flush_fcb(fcb *fcb, BOOL cache, LIST_ENTRY *batchlist, PIRP Irp)
Definition: flushthread.c:4628
void clear_rollback(LIST_ENTRY *rollback)
Definition: treefuncs.c:1028
BOOL changed
Definition: btrfs_drv.h:548
#define max(a, b)
Definition: svc.c:63
struct S2 s2
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
BOOL write
Definition: btrfs_drv.h:415
NTSYSAPI void WINAPI RtlInitializeBitMap(PRTL_BITMAP, PULONG, ULONG)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
UINT64 offset
Definition: btrfs.h:125
#define FREE_SPACE_EXTENT
Definition: btrfs.h:418
static void order_space_entry(space *s, LIST_ENTRY *list_size)
Definition: free-space.c:286
Definition: btrfs.h:421
void space_list_subtract2(LIST_ENTRY *list, LIST_ENTRY *list_size, UINT64 address, UINT64 length, chunk *c, LIST_ENTRY *rollback)
Definition: free-space.c:1940
void free_fcb(_Inout_ fcb *fcb)
Definition: btrfs.c:1507
#define BTRFS_INODE_NODATACOW
Definition: propsheet.h:77
#define BTRFS_COMPRESSION_NONE
Definition: btrfs.h:58
NTSTATUS excise_extents(device_extension *Vcb, fcb *fcb, UINT64 start_data, UINT64 end_data, PIRP Irp, LIST_ENTRY *rollback)
Definition: write.c:2376
void space_list_add(chunk *c, UINT64 address, UINT64 length, LIST_ENTRY *rollback)
Definition: free-space.c:1931
#define CACHE_INCREMENTS
Definition: free-space.c:22
EXTENT_DATA2 * ed2
Definition: write.c:2827
static NTSTATUS get_superblock_size(chunk *c, UINT64 *size)
Definition: free-space.c:351
_In_ PIRP Irp
Definition: csq.h:116
UINT64 size
Definition: btrfs.h:342
BOOL find_next_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *next_tp, BOOL ignore, PIRP Irp)
Definition: treefuncs.c:592
struct _LIST_ENTRY * Blink
Definition: typedefs.h:120
FORCEINLINE VOID InsertHeadList(_Inout_ PLIST_ENTRY ListHead, _Inout_ __drv_aliasesMem PLIST_ENTRY Entry)
Definition: rtlfuncs.h:201
int ignore(int trapCode, ppc_trap_frame_t *trap)
Definition: mmuobject.c:296
fcb * create_fcb(device_extension *Vcb, POOL_TYPE pool_type)
Definition: create.c:45
#define keycmp(key1, key2)
Definition: btrfs_drv.h:1004
#define WARN(fmt,...)
Definition: debug.h:111
LONG NTSTATUS
Definition: precomp.h:26
UINT64 offset
Definition: btrfs.h:422
GLintptr offset
Definition: glext.h:5920
NTSTATUS flush_partial_stripe(device_extension *Vcb, chunk *c, partial_stripe *ps)
Definition: flushthread.c:5599
LIST_ENTRY list_entry
Definition: free-space.c:312
release_chunk_lock(c, Vcb)
UINT64 obj_id
Definition: btrfs.h:123
NTSTATUS update_chunk_caches_tree(device_extension *Vcb, PIRP Irp)
Definition: free-space.c:1889
UINT32 crc32
Definition: btrfs.c:3897
#define BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID
Definition: btrfs.h:101
#define FREE_SPACE_CACHE_ID
Definition: btrfs.h:81
GLuint GLuint end
Definition: gl.h:1545
_In_ UINT64 _In_ UINT64 _In_ UINT64 _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2663
__u16 time
Definition: mkdosfs.c:366
#define InsertTailList(ListHead, Entry)
#define TYPE_METADATA_ITEM
Definition: btrfs.h:30
UINT64 offset
Definition: btrfs.h:326
UINT16 size
Definition: btrfs_drv.h:389
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
static uint32_t calc_crc32c(uint32_t seed, uint8_t *msg, ULONG msglen)
Definition: recv.cpp:134
UINT8 obj_type
Definition: btrfs.h:124
Definition: fs.h:78
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
Definition: rtlfuncs.h:105
UINT64 size
Definition: btrfs_drv.h:485
BOOLEAN NTAPI ExAcquireResourceExclusiveLite(IN PERESOURCE Resource, IN BOOLEAN Wait)
Definition: resource.c:770
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:451
#define ALLOC_TAG
Definition: btrfs_drv.h:86
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
tree * tree
Definition: btrfs_drv.h:474
chunk * chunk
Definition: btrfs_drv.h:1223
unsigned int UINT32
chunk * get_chunk_from_address(device_extension *Vcb, UINT64 address)
Definition: write.c:93
unsigned int BOOL
Definition: ntddk_ex.h:94
time_t now
Definition: finger.c:65
void space_list_add2(LIST_ENTRY *list, LIST_ENTRY *list_size, UINT64 address, UINT64 length, chunk *c, LIST_ENTRY *rollback)
Definition: free-space.c:1415
#define FREE_SPACE_BITMAP
Definition: btrfs.h:419
UINT64 address
Definition: btrfs.h:341
NTSTATUS open_fcb(_Requires_lock_held_(_Curr_->tree_lock) _Requires_exclusive_lock_held_(_Curr_->fcb_lock) device_extension *Vcb, root *subvol, UINT64 inode, UINT8 type, PANSI_STRING utf8, fcb *parent, fcb **pfcb, POOL_TYPE pooltype, PIRP Irp)
Definition: create.c:595
NTSTATUS add_space_entry(LIST_ENTRY *list, LIST_ENTRY *list_size, UINT64 offset, UINT64 size)
Definition: free-space.c:189
NTSYSAPI ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP, ULONG, PULONG)
UINT8 type
Definition: btrfs.h:424
void reap_fcb(fcb *fcb)
Definition: btrfs.c:1520
smooth NULL
Definition: ftsmooth.c:416
char ext[3]
Definition: mkdosfs.c:358
#define TYPE_EXTENT_ITEM
Definition: btrfs.h:29
void mark_fcb_dirty(_In_ fcb *fcb)
Definition: btrfs.c:1468
#define BLOCK_FLAG_RAID10
Definition: shellext.h:76
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
GLuint index
Definition: glext.h:6031
NTSTATUS do_write_file(fcb *fcb, UINT64 start_data, UINT64 end_data, void *data, PIRP Irp, BOOL file_write, UINT32 irp_offset, LIST_ENTRY *rollback)
Definition: write.c:3947
BOOL readonly
Definition: btrfs_drv.h:544
static NTSTATUS update_chunk_cache_tree(device_extension *Vcb, chunk *c, LIST_ENTRY *batchlist)
Definition: free-space.c:1767
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
NTSTATUS commit_batch_list(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, LIST_ENTRY *batchlist, PIRP Irp)
Definition: treefuncs.c:2280
#define b
Definition: ke_i.h:79
UINT16 sub_stripes
Definition: btrfs.h:321
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
NTSTATUS update_chunk_caches(device_extension *Vcb, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:1819
static LONG find_item(PropertyBag *This, LPCOLESTR name)
Definition: propertybag.c:110
static void add_rollback_space(LIST_ENTRY *rollback, BOOL add, LIST_ENTRY *list, LIST_ENTRY *list_size, UINT64 address, UINT64 length, chunk *c)
Definition: free-space.c:1397
#define BLOCK_FLAG_RAID0
Definition: shellext.h:73
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define STATUS_NOT_FOUND
Definition: shellext.h:67
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define TRACE(s)
Definition: solgame.cpp:4
#define InterlockedIncrement64
Definition: interlocked.h:211
GLsizeiptr size
Definition: glext.h:5919
#define S_IWUSR
Definition: propsheet.h:33
struct _fcb fcb
Definition: btrfs_drv.h:1334
void clear_batch_list(device_extension *Vcb, LIST_ENTRY *batchlist)
Definition: treefuncs.c:1203
static NTSTATUS allocate_cache_chunk(device_extension *Vcb, chunk *c, BOOL *changed, LIST_ENTRY *batchlist, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:1015
if(!(yy_init))
Definition: macro.lex.yy.c:714
static const UINT64 superblock_addrs[]
Definition: btrfs.h:12
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
#define TYPE_FREE_SPACE_EXTENT
Definition: btrfs.h:38
#define BTRFS_INODE_NODATASUM
Definition: propsheet.h:76
static void load_free_space_bitmap(device_extension *Vcb, chunk *c, UINT64 offset, void *data, UINT64 *total_space)
Definition: free-space.c:257
#define Vcb
Definition: cdprocs.h:1425
const GLubyte * c
Definition: glext.h:8905
UINT64 type
Definition: btrfs.h:316
GLuint address
Definition: glext.h:9393
BOOL deleted
Definition: btrfs_drv.h:268
VOID FASTCALL ExReleaseResourceLite(IN PERESOURCE Resource)
Definition: resource.c:1817
#define BLOCK_FLAG_RAID6
Definition: shellext.h:78
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
BITMAP bmp
Definition: alphablend.c:62
GLbitfield flags
Definition: glext.h:7161
NTSTATUS read_file(fcb *fcb, UINT8 *data, UINT64 start, UINT64 length, ULONG *pbr, PIRP Irp)
Definition: read.c:2737
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
NTSTATUS allocate_cache(device_extension *Vcb, BOOL *changed, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:1351
tree_data * item
Definition: btrfs_drv.h:475
UINT64 size
Definition: btrfs.h:423
GLenum const GLvoid * addr
Definition: glext.h:9621
#define index(s, c)
Definition: various.h:29
void protect_superblocks(_Inout_ chunk *c)
Definition: btrfs.c:3434
#define BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE
Definition: btrfs.h:100
#define TYPE_INODE_ITEM
Definition: btrfs.h:18
GLenum GLsizei len
Definition: glext.h:6722
#define TYPE_FREE_SPACE_INFO
Definition: btrfs.h:37
GLdouble s
Definition: gl.h:2039
Definition: _list.h:228
Definition: typedefs.h:117
#define EXTENT_TYPE_PREALLOC
Definition: btrfs.h:69
INODE_ITEM inode_item
Definition: btrfs_drv.h:265
NTSTATUS insert_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _In_ UINT64 obj_id, _In_ UINT8 obj_type, _In_ UINT64 offset, _In_reads_bytes_opt_(size) _When_(return >=0, __drv_aliasesMem) void *data, _In_ UINT16 size, _Out_opt_ traverse_ptr *ptp, _In_opt_ PIRP Irp)
Definition: treefuncs.c:857
_In_ fcb _In_ chunk _In_ UINT64 _In_ UINT64 _In_ BOOL _In_opt_ void _In_opt_ PIRP _In_ LIST_ENTRY * rollback
Definition: btrfs_drv.h:1334
NTSTATUS alloc_chunk(device_extension *Vcb, UINT64 flags, chunk **pc, BOOL full_size)
Definition: write.c:365
static void space_list_merge(LIST_ENTRY *spacelist, LIST_ENTRY *spacelist_size, LIST_ENTRY *deleting)
Definition: free-space.c:1626
UINT32 flags
Definition: btrfs.h:509
#define EXTENT_TYPE_REGULAR
Definition: btrfs.h:68
#define __S_IFREG
Definition: btrfs_drv.h:1708
Status
Definition: gdiplustypes.h:24
UINT64 address
Definition: btrfs_drv.h:484
#define ERR(fmt,...)
Definition: debug.h:109
Definition: btrfs.h:122
UINT64 stripe_length
Definition: btrfs.h:315
UINT64 st_size
Definition: btrfs.h:267
BOOL reloc
Definition: btrfs_drv.h:545
#define acquire_chunk_lock(c, Vcb)
Definition: btrfs_drv.h:1117
UINT64 num_bitmaps
Definition: btrfs.h:431
GLuint start
Definition: gl.h:1545
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
_In_ UINT64 _In_ UINT64 _In_ UINT64 generation
Definition: btrfs.c:2662
NTSTATUS load_stored_free_space_cache(device_extension *Vcb, chunk *c, BOOL load_only, PIRP Irp)
Definition: free-space.c:453
NTSYSAPI ULONG NTAPI RtlFindFirstRunClear(_In_ PRTL_BITMAP BitMapHeader, _Out_ PULONG StartingIndex)
#define list
Definition: rosglue.h:35
#define S_IRUSR
Definition: propsheet.h:29
unsigned short UINT16
Definition: list.h:27
static NTSTATUS load_free_space_cache(device_extension *Vcb, chunk *c, PIRP Irp)
Definition: free-space.c:858
static NTSTATUS load_stored_free_space_tree(device_extension *Vcb, chunk *c, PIRP Irp)
Definition: free-space.c:716
UINT64 address
Definition: btrfs_drv.h:1221
BOOLEAN NTAPI ExAcquireResourceSharedLite(IN PERESOURCE Resource, IN BOOLEAN Wait)
Definition: resource.c:885
#define BTRFS_TYPE_FILE
Definition: shellext.h:80
void space_list_subtract(chunk *c, BOOL deleting, UINT64 address, UINT64 length, LIST_ENTRY *rollback)
Definition: free-space.c:2019
LIST_ENTRY list_entry_size
Definition: btrfs_drv.h:487
#define BTRFS_INODE_PREALLOC
Definition: propsheet.h:80
#define STATUS_DISK_FULL
Definition: udferr_usr.h:155
static __inline void win_time_to_unix(LARGE_INTEGER t, BTRFS_TIME *out)
Definition: btrfs_drv.h:977
static NTSTATUS remove_free_space_inode(device_extension *Vcb, UINT64 inode, LIST_ENTRY *batchlist, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:24
#define c
Definition: ke_i.h:80
UINT64 generation
Definition: btrfs.h:429
unsigned int ULONG
Definition: retypes.h:1
LIST_ENTRY list_entry
Definition: btrfs_drv.h:486
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
LIST_ENTRY * list
Definition: btrfs_drv.h:1219
UINT64 size
Definition: btrfs.h:313
UINT64 num_entries
Definition: btrfs.h:430
BOOL space_changed
Definition: btrfs_drv.h:549
#define fast_io_possible(fcb)
Definition: btrfs_drv.h:1618
NTSTATUS load_cache_chunk(device_extension *Vcb, chunk *c, PIRP Irp)
Definition: free-space.c:952
static NTSTATUS add_superblock_stripe(LIST_ENTRY *stripes, UINT64 off, UINT64 len)
Definition: free-space.c:315
#define BLOCK_FLAG_RAID5
Definition: shellext.h:77
unsigned long long UINT64
#define ss
Definition: i386-dis.c:432
return STATUS_SUCCESS
Definition: btrfs.c:2745
void add_rollback(_In_ LIST_ENTRY *rollback, _In_ enum rollback_type type, _In_ __drv_aliasesMem void *ptr)
Definition: treefuncs.c:836
NTSTATUS insert_tree_item_batch(LIST_ENTRY *batchlist, device_extension *Vcb, root *r, UINT64 objid, UINT8 objtype, UINT64 offset, _In_opt_ _When_(return >=0, __drv_aliasesMem) void *data, UINT16 datalen, enum batch_operation operation)
Definition: flushthread.c:4258
unsigned char UINT8
UINT16 num_stripes
Definition: btrfs.h:320
static uint64_t __inline sector_align(uint64_t n, uint64_t a)
#define BTRFS_INODE_NOCOMPRESS
Definition: propsheet.h:79
static NTSTATUS update_chunk_cache(device_extension *Vcb, chunk *c, BTRFS_TIME *now, LIST_ENTRY *batchlist, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:1641
UINT8 * data
Definition: btrfs_drv.h:390
struct _device_extension * Vcb
Definition: btrfs_drv.h:260
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
NTSTATUS clear_free_space_cache(device_extension *Vcb, LIST_ENTRY *batchlist, PIRP Irp)
Definition: free-space.c:58
#define TYPE_FREE_SPACE_BITMAP
Definition: btrfs.h:39
NTSTATUS delete_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _Inout_ traverse_ptr *tp)
Definition: treefuncs.c:989
Definition: path.c:42
off
Definition: i386-dis.c:3909