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