ReactOS  0.4.14-dev-115-g4576127
treefuncs.c File Reference
#include "btrfs_drv.h"
Include dependency graph for treefuncs.c:

Go to the source code of this file.

Functions

NTSTATUS load_tree (device_extension *Vcb, uint64_t addr, uint8_t *buf, root *r, tree **pt)
 
static NTSTATUS do_load_tree2 (device_extension *Vcb, tree_holder *th, uint8_t *buf, root *r, tree *t, tree_data *td)
 
NTSTATUS do_load_tree (device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
 
void free_tree (tree *t)
 
static __inline tree_datafirst_item (tree *t)
 
static __inline tree_dataprev_item (tree *t, tree_data *td)
 
static __inline tree_datanext_item (tree *t, tree_data *td)
 
static NTSTATUS next_item2 (device_extension *Vcb, tree *t, tree_data *td, traverse_ptr *tp)
 
NTSTATUS skip_to_difference (device_extension *Vcb, traverse_ptr *tp, traverse_ptr *tp2, bool *ended1, bool *ended2)
 
static NTSTATUS find_item_in_tree (device_extension *Vcb, tree *t, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
 
NTSTATUS find_item (_In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _Out_ traverse_ptr *tp, _In_ const KEY *searchkey, _In_ bool ignore, _In_opt_ PIRP Irp)
 
NTSTATUS find_item_to_level (device_extension *Vcb, root *r, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
 
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)
 
static __inline tree_datalast_item (tree *t)
 
bool find_prev_item (_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *prev_tp, PIRP Irp)
 
void free_trees_root (device_extension *Vcb, root *r)
 
void free_trees (device_extension *Vcb)
 
void add_rollback (_In_ LIST_ENTRY *rollback, _In_ enum rollback_type type, _In_ __drv_aliasesMem void *ptr)
 
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)
 
NTSTATUS delete_tree_item (_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _Inout_ traverse_ptr *tp)
 
void clear_rollback (LIST_ENTRY *rollback)
 
void do_rollback (device_extension *Vcb, LIST_ENTRY *rollback)
 
static void find_tree_end (tree *t, KEY *tree_end, bool *no_end)
 
void clear_batch_list (device_extension *Vcb, LIST_ENTRY *batchlist)
 
static void add_delete_inode_extref (device_extension *Vcb, batch_item *bi, LIST_ENTRY *listhead)
 
static NTSTATUS handle_batch_collision (device_extension *Vcb, batch_item *bi, tree *t, tree_data *td, tree_data *newtd, LIST_ENTRY *listhead, bool *ignore)
 
static NTSTATUS commit_batch_list_root (_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, batch_root *br, PIRP Irp)
 
NTSTATUS commit_batch_list (_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, LIST_ENTRY *batchlist, PIRP Irp)
 

Function Documentation

◆ add_delete_inode_extref()

static void add_delete_inode_extref ( device_extension Vcb,
batch_item bi,
LIST_ENTRY listhead 
)
static

Definition at line 1219 of file treefuncs.c.

1219  {
1220  batch_item* bi2;
1221  LIST_ENTRY* le;
1222  INODE_REF* delir = (INODE_REF*)bi->data;
1223  INODE_EXTREF* ier;
1224 
1225  TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1226 
1227  bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
1228  if (!bi2) {
1229  ERR("out of memory\n");
1230  return;
1231  }
1232 
1233  ier = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_EXTREF) - 1 + delir->n, ALLOC_TAG);
1234  if (!ier) {
1235  ERR("out of memory\n");
1236  ExFreePool(bi2);
1237  return;
1238  }
1239 
1240  ier->dir = bi->key.offset;
1241  ier->index = delir->index;
1242  ier->n = delir->n;
1243  RtlCopyMemory(ier->name, delir->name, delir->n);
1244 
1245  bi2->key.obj_id = bi->key.obj_id;
1247  bi2->key.offset = calc_crc32c((uint32_t)bi->key.offset, (uint8_t*)ier->name, ier->n);
1248  bi2->data = ier;
1249  bi2->datalen = sizeof(INODE_EXTREF) - 1 + ier->n;
1251 
1252  le = bi->list_entry.Flink;
1253  while (le != listhead) {
1255 
1256  if (keycmp(bi3->key, bi2->key) != -1) {
1257  InsertHeadList(le->Blink, &bi2->list_entry);
1258  return;
1259  }
1260 
1261  le = le->Flink;
1262  }
1263 
1264  InsertTailList(listhead, &bi2->list_entry);
1265 }
LIST_ENTRY list_entry
Definition: btrfs_drv.h:485
uint64_t obj_id
Definition: btrfs.h:127
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
uint8_t obj_type
Definition: btrfs.h:128
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
#define keycmp(key1, key2)
Definition: btrfs_drv.h:980
enum batch_operation operation
Definition: btrfs_drv.h:484
#define InsertTailList(ListHead, Entry)
uint64_t offset
Definition: btrfs.h:129
static uint32_t calc_crc32c(uint32_t seed, uint8_t *msg, ULONG msglen)
Definition: recv.cpp:134
void * data
Definition: btrfs_drv.h:482
#define ALLOC_TAG
Definition: btrfs_drv.h:91
while(1)
Definition: macro.lex.yy.c:740
char name[1]
Definition: btrfs.h:354
uint16_t n
Definition: btrfs.h:353
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
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define TRACE(s)
Definition: solgame.cpp:4
#define Vcb
Definition: cdprocs.h:1425
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define TYPE_INODE_EXTREF
Definition: btrfs.h:21
Definition: typedefs.h:117
BYTE uint8_t
Definition: msvideo1.c:66
#define ERR(fmt,...)
Definition: debug.h:109
uint64_t index
Definition: btrfs.h:352
Definition: list.h:27
UINT32 uint32_t
Definition: types.h:75
uint16_t datalen
Definition: btrfs_drv.h:483
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

Referenced by commit_batch_list_root(), and handle_batch_collision().

◆ add_rollback()

void add_rollback ( _In_ LIST_ENTRY rollback,
_In_ enum rollback_type  type,
_In_ __drv_aliasesMem void ptr 
)

Definition at line 836 of file treefuncs.c.

836  {
837  rollback_item* ri;
838 
840  if (!ri) {
841  ERR("out of memory\n");
842  return;
843  }
844 
845  ri->type = type;
846  ri->ptr = ptr;
848 }
enum rollback_type type
Definition: btrfs_drv.h:1218
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
#define InsertTailList(ListHead, Entry)
#define ALLOC_TAG
Definition: btrfs_drv.h:91
static PVOID ptr
Definition: dispmode.c:27
LIST_ENTRY list_entry
Definition: btrfs_drv.h:1220
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define ERR(fmt,...)
Definition: debug.h:109
_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

Referenced by add_insert_extent_rollback(), add_rollback_space(), and remove_fcb_extent().

◆ clear_batch_list()

void clear_batch_list ( device_extension Vcb,
LIST_ENTRY batchlist 
)

Definition at line 1203 of file treefuncs.c.

1203  {
1204  while (!IsListEmpty(batchlist)) {
1205  LIST_ENTRY* le = RemoveHeadList(batchlist);
1207 
1208  while (!IsListEmpty(&br->items)) {
1209  LIST_ENTRY* le2 = RemoveHeadList(&br->items);
1211 
1212  ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi);
1213  }
1214 
1215  ExFreePool(br);
1216  }
1217 }
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
LIST_ENTRY items
Definition: btrfs_drv.h:490
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
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
#define Vcb
Definition: cdprocs.h:1425
Definition: typedefs.h:117
Definition: list.h:27
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

Referenced by allocate_cache(), do_write2(), mount_vol(), update_chunk_caches(), update_chunk_caches_tree(), and update_chunk_usage().

◆ clear_rollback()

void clear_rollback ( LIST_ENTRY rollback)

Definition at line 1028 of file treefuncs.c.

1028  {
1029  while (!IsListEmpty(rollback)) {
1032 
1033  switch (ri->type) {
1034  case ROLLBACK_ADD_SPACE:
1038  ExFreePool(ri->ptr);
1039  break;
1040 
1041  default:
1042  break;
1043  }
1044 
1045  ExFreePool(ri);
1046  }
1047 }
enum rollback_type type
Definition: btrfs_drv.h:1218
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
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
Definition: typedefs.h:117
Definition: list.h:27
_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
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

Referenced by _Dispatch_type_(), balance_data_chunk(), balance_metadata_chunk(), check_for_orphans_root(), clear_free_space_cache(), delete_reparse_point(), do_create_snapshot(), do_write(), duplicate_extents(), load_stored_free_space_cache(), set_end_of_file_information(), set_link_information(), set_rename_information(), set_reparse_point(), set_valid_data_length_information(), set_zero_data(), and write_file().

◆ commit_batch_list()

NTSTATUS commit_batch_list ( _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension Vcb,
LIST_ENTRY batchlist,
PIRP  Irp 
)

Definition at line 2280 of file treefuncs.c.

2280  {
2281  NTSTATUS Status;
2282 
2283  while (!IsListEmpty(batchlist)) {
2284  LIST_ENTRY* le = RemoveHeadList(batchlist);
2286 
2288  if (!NT_SUCCESS(Status)) {
2289  ERR("commit_batch_list_root returned %08x\n", Status);
2290  return Status;
2291  }
2292 
2293  ExFreePool(br2);
2294  }
2295 
2296  return STATUS_SUCCESS;
2297 }
_In_ PIRP Irp
Definition: csq.h:116
LONG NTSTATUS
Definition: precomp.h:26
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
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
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
Definition: typedefs.h:117
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
static NTSTATUS commit_batch_list_root(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, batch_root *br, PIRP Irp)
Definition: treefuncs.c:1851
Definition: list.h:27
return STATUS_SUCCESS
Definition: btrfs.c:2966
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

Referenced by allocate_cache(), do_write2(), mount_vol(), update_chunk_caches(), update_chunk_caches_tree(), and update_chunk_usage().

◆ commit_batch_list_root()

static NTSTATUS commit_batch_list_root ( _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension Vcb,
batch_root br,
PIRP  Irp 
)
static

Definition at line 1851 of file treefuncs.c.

1851  {
1852  LIST_ENTRY* le;
1853  NTSTATUS Status;
1854 
1855  TRACE("root: %I64x\n", br->r->id);
1856 
1857  le = br->items.Flink;
1858  while (le != &br->items) {
1860  LIST_ENTRY *le2;
1861  traverse_ptr tp;
1862  KEY tree_end;
1863  bool no_end;
1864  tree_data *td, *listhead;
1865  int cmp;
1866  tree* t;
1867  bool ignore = false;
1868 
1869  TRACE("(%I64x,%x,%I64x)\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1870 
1871  Status = find_item(Vcb, br->r, &tp, &bi->key, true, Irp);
1872  if (!NT_SUCCESS(Status)) { // FIXME - handle STATUS_NOT_FOUND
1873  ERR("find_item returned %08x\n", Status);
1874  return Status;
1875  }
1876 
1877  find_tree_end(tp.tree, &tree_end, &no_end);
1878 
1879  if (bi->operation == Batch_DeleteInode) {
1880  if (tp.item->key.obj_id == bi->key.obj_id) {
1881  bool ended = false;
1882 
1883  td = tp.item;
1884 
1885  if (!tp.item->ignore) {
1886  tp.item->ignore = true;
1887  tp.tree->header.num_items--;
1888  tp.tree->size -= tp.item->size + sizeof(leaf_node);
1889  tp.tree->write = true;
1890  }
1891 
1892  le2 = tp.item->list_entry.Flink;
1893  while (le2 != &tp.tree->itemlist) {
1895 
1896  if (td->key.obj_id == bi->key.obj_id) {
1897  if (!td->ignore) {
1898  td->ignore = true;
1899  tp.tree->header.num_items--;
1900  tp.tree->size -= td->size + sizeof(leaf_node);
1901  tp.tree->write = true;
1902  }
1903  } else {
1904  ended = true;
1905  break;
1906  }
1907 
1908  le2 = le2->Flink;
1909  }
1910 
1911  while (!ended) {
1912  traverse_ptr next_tp;
1913 
1914  tp.item = td;
1915 
1916  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
1917  break;
1918 
1919  tp = next_tp;
1920 
1921  le2 = &tp.item->list_entry;
1922  while (le2 != &tp.tree->itemlist) {
1924 
1925  if (td->key.obj_id == bi->key.obj_id) {
1926  if (!td->ignore) {
1927  td->ignore = true;
1928  tp.tree->header.num_items--;
1929  tp.tree->size -= td->size + sizeof(leaf_node);
1930  tp.tree->write = true;
1931  }
1932  } else {
1933  ended = true;
1934  break;
1935  }
1936 
1937  le2 = le2->Flink;
1938  }
1939  }
1940  }
1941  } else if (bi->operation == Batch_DeleteExtentData) {
1942  if (tp.item->key.obj_id < bi->key.obj_id || (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type < bi->key.obj_type)) {
1943  traverse_ptr tp2;
1944 
1945  if (find_next_item(Vcb, &tp, &tp2, false, Irp)) {
1946  if (tp2.item->key.obj_id == bi->key.obj_id && tp2.item->key.obj_type == bi->key.obj_type) {
1947  tp = tp2;
1948  find_tree_end(tp.tree, &tree_end, &no_end);
1949  }
1950  }
1951  }
1952 
1953  if (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type == bi->key.obj_type) {
1954  bool ended = false;
1955 
1956  td = tp.item;
1957 
1958  if (!tp.item->ignore) {
1959  tp.item->ignore = true;
1960  tp.tree->header.num_items--;
1961  tp.tree->size -= tp.item->size + sizeof(leaf_node);
1962  tp.tree->write = true;
1963  }
1964 
1965  le2 = tp.item->list_entry.Flink;
1966  while (le2 != &tp.tree->itemlist) {
1968 
1969  if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
1970  if (!td->ignore) {
1971  td->ignore = true;
1972  tp.tree->header.num_items--;
1973  tp.tree->size -= td->size + sizeof(leaf_node);
1974  tp.tree->write = true;
1975  }
1976  } else {
1977  ended = true;
1978  break;
1979  }
1980 
1981  le2 = le2->Flink;
1982  }
1983 
1984  while (!ended) {
1985  traverse_ptr next_tp;
1986 
1987  tp.item = td;
1988 
1989  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
1990  break;
1991 
1992  tp = next_tp;
1993 
1994  le2 = &tp.item->list_entry;
1995  while (le2 != &tp.tree->itemlist) {
1997 
1998  if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
1999  if (!td->ignore) {
2000  td->ignore = true;
2001  tp.tree->header.num_items--;
2002  tp.tree->size -= td->size + sizeof(leaf_node);
2003  tp.tree->write = true;
2004  }
2005  } else {
2006  ended = true;
2007  break;
2008  }
2009 
2010  le2 = le2->Flink;
2011  }
2012  }
2013  }
2014  } else if (bi->operation == Batch_DeleteFreeSpace) {
2015  if (tp.item->key.obj_id >= bi->key.obj_id && tp.item->key.obj_id < bi->key.obj_id + bi->key.offset) {
2016  bool ended = false;
2017 
2018  td = tp.item;
2019 
2020  if (!tp.item->ignore) {
2021  tp.item->ignore = true;
2022  tp.tree->header.num_items--;
2023  tp.tree->size -= tp.item->size + sizeof(leaf_node);
2024  tp.tree->write = true;
2025  }
2026 
2027  le2 = tp.item->list_entry.Flink;
2028  while (le2 != &tp.tree->itemlist) {
2030 
2031  if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2032  if (!td->ignore) {
2033  td->ignore = true;
2034  tp.tree->header.num_items--;
2035  tp.tree->size -= td->size + sizeof(leaf_node);
2036  tp.tree->write = true;
2037  }
2038  } else {
2039  ended = true;
2040  break;
2041  }
2042 
2043  le2 = le2->Flink;
2044  }
2045 
2046  while (!ended) {
2047  traverse_ptr next_tp;
2048 
2049  tp.item = td;
2050 
2051  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
2052  break;
2053 
2054  tp = next_tp;
2055 
2056  le2 = &tp.item->list_entry;
2057  while (le2 != &tp.tree->itemlist) {
2059 
2060  if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2061  if (!td->ignore) {
2062  td->ignore = true;
2063  tp.tree->header.num_items--;
2064  tp.tree->size -= td->size + sizeof(leaf_node);
2065  tp.tree->write = true;
2066  }
2067  } else {
2068  ended = true;
2069  break;
2070  }
2071 
2072  le2 = le2->Flink;
2073  }
2074  }
2075  }
2076  } else {
2079  td = NULL;
2080  else {
2081  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2082  if (!td) {
2083  ERR("out of memory\n");
2085  }
2086 
2087  td->key = bi->key;
2088  td->size = bi->datalen;
2089  td->data = bi->data;
2090  td->ignore = false;
2091  td->inserted = true;
2092  }
2093 
2094  cmp = keycmp(bi->key, tp.item->key);
2095 
2096  if (cmp == -1) { // very first key in root
2097  if (td) {
2098  tree_data* paritem;
2099 
2101 
2102  paritem = tp.tree->paritem;
2103  while (paritem) {
2104  if (!keycmp(paritem->key, tp.item->key)) {
2105  paritem->key = bi->key;
2106  } else
2107  break;
2108 
2109  paritem = paritem->treeholder.tree->paritem;
2110  }
2111  }
2112  } else if (cmp == 0) { // item already exists
2113  if (tp.item->ignore) {
2114  if (td)
2116  } else {
2117  Status = handle_batch_collision(Vcb, bi, tp.tree, tp.item, td, &br->items, &ignore);
2118  if (!NT_SUCCESS(Status)) {
2119  ERR("handle_batch_collision returned %08x\n", Status);
2120 
2121  if (td)
2122  ExFreeToPagedLookasideList(&Vcb->tree_data_lookaside, td);
2123 
2124  return Status;
2125  }
2126  }
2127  } else if (td) {
2129  }
2130 
2131  if (bi->operation == Batch_DeleteInodeRef && cmp != 0 && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2132  add_delete_inode_extref(Vcb, bi, &br->items);
2133  }
2134 
2135  if (!ignore && td) {
2136  tp.tree->header.num_items++;
2137  tp.tree->size += bi->datalen + sizeof(leaf_node);
2138  tp.tree->write = true;
2139 
2140  listhead = td;
2141  } else
2142  listhead = tp.item;
2143 
2144  while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2146 
2147  if (!keycmp(prevtd->key, listhead->key))
2148  listhead = prevtd;
2149  else
2150  break;
2151  }
2152 
2153  le2 = le->Flink;
2154  while (le2 != &br->items) {
2156 
2158  break;
2159 
2160  if (no_end || keycmp(bi2->key, tree_end) == -1) {
2161  LIST_ENTRY* le3;
2162  bool inserted = false;
2163 
2164  ignore = false;
2165 
2168  td = NULL;
2169  else {
2170  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2171  if (!td) {
2172  ERR("out of memory\n");
2174  }
2175 
2176  td->key = bi2->key;
2177  td->size = bi2->datalen;
2178  td->data = bi2->data;
2179  td->ignore = false;
2180  td->inserted = true;
2181  }
2182 
2183  le3 = &listhead->list_entry;
2184  while (le3 != &tp.tree->itemlist) {
2186 
2187  cmp = keycmp(bi2->key, td2->key);
2188 
2189  if (cmp == 0) {
2190  if (td2->ignore) {
2191  if (td) {
2192  InsertHeadList(le3->Blink, &td->list_entry);
2193  inserted = true;
2194  } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2195  add_delete_inode_extref(Vcb, bi2, &br->items);
2196  }
2197  } else {
2198  Status = handle_batch_collision(Vcb, bi2, tp.tree, td2, td, &br->items, &ignore);
2199  if (!NT_SUCCESS(Status)) {
2200  ERR("handle_batch_collision returned %08x\n", Status);
2201  return Status;
2202  }
2203  }
2204 
2205  inserted = true;
2206  break;
2207  } else if (cmp == -1) {
2208  if (td) {
2209  InsertHeadList(le3->Blink, &td->list_entry);
2210  inserted = true;
2211  } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2212  add_delete_inode_extref(Vcb, bi2, &br->items);
2213  }
2214  break;
2215  }
2216 
2217  le3 = le3->Flink;
2218  }
2219 
2220  if (td) {
2221  if (!inserted)
2223 
2224  if (!ignore) {
2225  tp.tree->header.num_items++;
2226  tp.tree->size += bi2->datalen + sizeof(leaf_node);
2227 
2228  listhead = td;
2229  }
2230  } else if (!inserted && bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2231  add_delete_inode_extref(Vcb, bi2, &br->items);
2232  }
2233 
2234  while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2236 
2237  if (!keycmp(prevtd->key, listhead->key))
2238  listhead = prevtd;
2239  else
2240  break;
2241  }
2242 
2243  le = le2;
2244  } else
2245  break;
2246 
2247  le2 = le2->Flink;
2248  }
2249 
2250  t = tp.tree;
2251  while (t) {
2252  if (t->paritem && t->paritem->ignore) {
2253  t->paritem->ignore = false;
2254  t->parent->header.num_items++;
2255  t->parent->size += sizeof(internal_node);
2256  }
2257 
2258  t->header.generation = Vcb->superblock.generation;
2259  t = t->parent;
2260  }
2261  }
2262 
2263  le = le->Flink;
2264  }
2265 
2266  // FIXME - remove as we are going along
2267  while (!IsListEmpty(&br->items)) {
2269 
2272  ExFreePool(bi->data);
2273 
2274  ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi);
2275  }
2276 
2277  return STATUS_SUCCESS;
2278 }
uint64_t obj_id
Definition: btrfs.h:127
uint8_t obj_type
Definition: btrfs.h:128
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
_In_ PIRP Irp
Definition: csq.h:116
bool inserted
Definition: btrfs_drv.h:403
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
#define BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF
Definition: btrfs.h:111
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
#define keycmp(key1, key2)
Definition: btrfs_drv.h:980
LONG NTSTATUS
Definition: precomp.h:26
tree_holder treeholder
Definition: btrfs_drv.h:406
uint16_t size
Definition: btrfs_drv.h:409
enum batch_operation operation
Definition: btrfs_drv.h:484
NTSTATUS find_item(_In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _Out_ traverse_ptr *tp, _In_ const KEY *searchkey, _In_ bool ignore, _In_opt_ PIRP Irp)
Definition: treefuncs.c:548
GLdouble GLdouble t
Definition: gl.h:2047
static void add_delete_inode_extref(device_extension *Vcb, batch_item *bi, LIST_ENTRY *listhead)
Definition: treefuncs.c:1219
#define cmp(status, error)
Definition: error.c:114
#define InsertTailList(ListHead, Entry)
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
uint64_t offset
Definition: btrfs.h:129
uint8_t * data
Definition: btrfs_drv.h:410
void * data
Definition: btrfs_drv.h:482
LIST_ENTRY list_entry
Definition: btrfs_drv.h:401
tree * tree
Definition: btrfs_drv.h:495
LIST_ENTRY items
Definition: btrfs_drv.h:490
uint64_t id
Definition: btrfs_drv.h:446
struct _tree * tree
Definition: btrfs_drv.h:396
tree_data * paritem
Definition: btrfs_drv.h:427
smooth NULL
Definition: ftsmooth.c:416
root * r
Definition: btrfs_drv.h:489
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
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
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define TRACE(s)
Definition: solgame.cpp:4
static NTSTATUS handle_batch_collision(device_extension *Vcb, batch_item *bi, tree *t, tree_data *td, tree_data *newtd, LIST_ENTRY *listhead, bool *ignore)
Definition: treefuncs.c:1267
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
LIST_ENTRY itemlist
Definition: btrfs_drv.h:429
#define Vcb
Definition: cdprocs.h:1425
tree_data * item
Definition: btrfs_drv.h:496
tree_header header
Definition: btrfs_drv.h:421
static void find_tree_end(tree *t, KEY *tree_end, bool *no_end)
Definition: treefuncs.c:1177
Definition: typedefs.h:117
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
bool ignore
Definition: btrfs_drv.h:402
uint32_t size
Definition: btrfs_drv.h:424
Definition: btrfs.h:126
Definition: list.h:27
uint32_t num_items
Definition: btrfs.h:144
uint16_t datalen
Definition: btrfs_drv.h:483
return STATUS_SUCCESS
Definition: btrfs.c:2966
bool write
Definition: btrfs_drv.h:435
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

Referenced by commit_batch_list().

◆ delete_tree_item()

NTSTATUS delete_tree_item ( _In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension Vcb,
_Inout_ traverse_ptr tp 
)

Definition at line 989 of file treefuncs.c.

989  {
990  tree* t;
991  uint64_t gen;
992 
993  TRACE("deleting item %I64x,%x,%I64x (ignore = %s)\n", tp->item->key.obj_id, tp->item->key.obj_type, tp->item->key.offset, tp->item->ignore ? "true" : "false");
994 
995 #ifdef DEBUG_PARANOID
996  if (tp->item->ignore) {
997  ERR("trying to delete already-deleted item %I64x,%x,%I64x\n", tp->item->key.obj_id, tp->item->key.obj_type, tp->item->key.offset);
998  int3;
999  return STATUS_INTERNAL_ERROR;
1000  }
1001 #endif
1002 
1003  tp->item->ignore = true;
1004 
1005  if (!tp->tree->write) {
1006  tp->tree->write = true;
1007  Vcb->need_write = true;
1008  }
1009 
1010  tp->tree->header.num_items--;
1011 
1012  if (tp->tree->header.level == 0)
1013  tp->tree->size -= sizeof(leaf_node) + tp->item->size;
1014  else
1015  tp->tree->size -= sizeof(internal_node);
1016 
1017  gen = tp->tree->Vcb->superblock.generation;
1018 
1019  t = tp->tree;
1020  while (t) {
1021  t->header.generation = gen;
1022  t = t->parent;
1023  }
1024 
1025  return STATUS_SUCCESS;
1026 }
uint64_t obj_id
Definition: btrfs.h:127
uint8_t obj_type
Definition: btrfs.h:128
#define int3
Definition: btrfs_drv.h:1653
uint16_t size
Definition: btrfs_drv.h:409
GLdouble GLdouble t
Definition: gl.h:2047
uint64_t offset
Definition: btrfs.h:129
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:451
struct _device_extension * Vcb
Definition: btrfs_drv.h:425
tree * tree
Definition: btrfs_drv.h:495
uint64_t generation
Definition: btrfs.h:142
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
#define TRACE(s)
Definition: solgame.cpp:4
#define Vcb
Definition: cdprocs.h:1425
uint8_t level
Definition: btrfs.h:145
tree_data * item
Definition: btrfs_drv.h:496
tree_header header
Definition: btrfs_drv.h:421
#define ERR(fmt,...)
Definition: debug.h:109
bool ignore
Definition: btrfs_drv.h:402
uint32_t size
Definition: btrfs_drv.h:424
UINT64 uint64_t
Definition: types.h:77
uint32_t num_items
Definition: btrfs.h:144
return STATUS_SUCCESS
Definition: btrfs.c:2966
bool write
Definition: btrfs_drv.h:435

Referenced by add_balance_item(), add_checksum_entry(), add_data_reloc(), add_device(), add_metadata_reloc(), add_parents(), add_root_item_to_cache(), add_root_ref(), allocate_cache_chunk(), check_for_orphans_root(), clear_free_space_cache(), convert_old_extent(), decrease_extent_refcount(), delete_root_ref(), drop_chunk(), drop_root(), finish_removing_device(), flush_changed_dev_stats(), flush_changed_extent(), flush_fcb(), flush_subvol(), increase_extent_refcount(), load_stored_free_space_cache(), remove_balance_item(), update_chunk_usage(), update_dev_item(), update_extent_level(), update_root_backref(), and write_metadata_items().

◆ do_load_tree()

NTSTATUS do_load_tree ( device_extension Vcb,
tree_holder th,
root r,
tree t,
tree_data td,
PIRP  Irp 
)

Definition at line 218 of file treefuncs.c.

218  {
220  uint8_t* buf;
221  chunk* c;
222 
223  buf = ExAllocatePoolWithTag(PagedPool, Vcb->superblock.node_size, ALLOC_TAG);
224  if (!buf) {
225  ERR("out of memory\n");
227  }
228 
229  Status = read_data(Vcb, th->address, Vcb->superblock.node_size, NULL, true, buf, NULL,
230  &c, Irp, th->generation, false, NormalPagePriority);
231  if (!NT_SUCCESS(Status)) {
232  ERR("read_data returned 0x%08x\n", Status);
233  ExFreePool(buf);
234  return Status;
235  }
236 
237  if (t)
238  ExAcquireFastMutex(&t->nonpaged->mutex);
239  else
240  ExAcquireResourceExclusiveLite(&r->nonpaged->load_tree_lock, true);
241 
242  Status = do_load_tree2(Vcb, th, buf, r, t, td);
243 
244  if (t)
245  ExReleaseFastMutex(&t->nonpaged->mutex);
246  else
247  ExReleaseResourceLite(&r->nonpaged->load_tree_lock);
248 
249  if (!th->tree || th->tree->buf != buf)
250  ExFreePool(buf);
251 
252  if (!NT_SUCCESS(Status)) {
253  ERR("do_load_tree2 returned %08x\n", Status);
254  return Status;
255  }
256 
257  return Status;
258 }
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
static NTSTATUS do_load_tree2(device_extension *Vcb, tree_holder *th, uint8_t *buf, root *r, tree *t, tree_data *td)
Definition: treefuncs.c:193
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
_In_ PIRP Irp
Definition: csq.h:116
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
LONG NTSTATUS
Definition: precomp.h:26
GLdouble GLdouble t
Definition: gl.h:2047
VOID FASTCALL ExReleaseFastMutex(IN PFAST_MUTEX FastMutex)
Definition: fmutex.c:31
BOOLEAN NTAPI ExAcquireResourceExclusiveLite(IN PERESOURCE Resource, IN BOOLEAN Wait)
Definition: resource.c:770
#define ALLOC_TAG
Definition: btrfs_drv.h:91
static BOOL read_data(request_t *request, void *buffer, DWORD size, DWORD *read, BOOL async)
Definition: request.c:2012
struct _tree * tree
Definition: btrfs_drv.h:396
smooth NULL
Definition: ftsmooth.c:416
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
const GLubyte * c
Definition: glext.h:8905
VOID FASTCALL ExReleaseResourceLite(IN PERESOURCE Resource)
Definition: resource.c:1817
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
BYTE uint8_t
Definition: msvideo1.c:66
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
VOID FASTCALL ExAcquireFastMutex(IN PFAST_MUTEX FastMutex)
Definition: fmutex.c:23
uint64_t address
Definition: btrfs_drv.h:394
#define c
Definition: ke_i.h:80
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
uint64_t generation
Definition: btrfs_drv.h:395

Referenced by find_item(), find_item_in_tree(), find_item_to_level(), find_next_item(), find_prev_item(), insert_tree_item(), and try_tree_amalgamate().

◆ do_load_tree2()

static NTSTATUS do_load_tree2 ( device_extension Vcb,
tree_holder th,
uint8_t buf,
root r,
tree t,
tree_data td 
)
static

Definition at line 193 of file treefuncs.c.

193  {
194  if (!th->tree) {
196  tree* nt;
197 
198  Status = load_tree(Vcb, th->address, buf, r, &nt);
199  if (!NT_SUCCESS(Status)) {
200  ERR("load_tree returned %08x\n", Status);
201  return Status;
202  }
203 
204  nt->parent = t;
205 
206 #ifdef DEBUG_PARANOID
207  if (t && t->header.level <= nt->header.level) int3;
208 #endif
209 
210  nt->paritem = td;
211 
212  th->tree = nt;
213  }
214 
215  return STATUS_SUCCESS;
216 }
NTSTATUS load_tree(device_extension *Vcb, uint64_t addr, uint8_t *buf, root *r, tree **pt)
Definition: treefuncs.c:20
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
LONG NTSTATUS
Definition: precomp.h:26
#define int3
Definition: btrfs_drv.h:1653
GLdouble GLdouble t
Definition: gl.h:2047
IMAGE_NT_HEADERS nt
Definition: module.c:50
struct _tree * tree
Definition: btrfs_drv.h:396
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
uint64_t address
Definition: btrfs_drv.h:394
return STATUS_SUCCESS
Definition: btrfs.c:2966

Referenced by do_load_tree().

◆ do_rollback()

void do_rollback ( device_extension Vcb,
LIST_ENTRY rollback 
)

Definition at line 1049 of file treefuncs.c.

1049  {
1050  NTSTATUS Status;
1051  rollback_item* ri;
1052 
1053  while (!IsListEmpty(rollback)) {
1056 
1057  switch (ri->type) {
1059  {
1060  rollback_extent* re = ri->ptr;
1061 
1062  re->ext->ignore = true;
1063 
1066 
1067  if (ed2->size != 0) {
1069 
1070  if (c) {
1072  re->fcb->inode, re->ext->offset - ed2->offset, -1,
1073  re->fcb->inode_item.flags & BTRFS_INODE_NODATASUM, false, NULL);
1074 
1075  if (!NT_SUCCESS(Status))
1076  ERR("update_changed_extent_ref returned %08x\n", Status);
1077  }
1078 
1080  }
1081  }
1082 
1083  ExFreePool(re);
1084  break;
1085  }
1086 
1088  {
1089  rollback_extent* re = ri->ptr;
1090 
1091  re->ext->ignore = false;
1092 
1095 
1096  if (ed2->size != 0) {
1098 
1099  if (c) {
1101  re->fcb->inode, re->ext->offset - ed2->offset, 1,
1102  re->fcb->inode_item.flags & BTRFS_INODE_NODATASUM, false, NULL);
1103 
1104  if (!NT_SUCCESS(Status))
1105  ERR("update_changed_extent_ref returned %08x\n", Status);
1106  }
1107 
1109  }
1110  }
1111 
1112  ExFreePool(re);
1113  break;
1114  }
1115 
1116  case ROLLBACK_ADD_SPACE:
1118  {
1119  rollback_space* rs = ri->ptr;
1120 
1121  if (rs->chunk)
1123 
1124  if (ri->type == ROLLBACK_ADD_SPACE)
1125  space_list_subtract2(rs->list, rs->list_size, rs->address, rs->length, NULL, NULL);
1126  else
1127  space_list_add2(rs->list, rs->list_size, rs->address, rs->length, NULL, NULL);
1128 
1129  if (rs->chunk) {
1130  if (ri->type == ROLLBACK_ADD_SPACE)
1131  rs->chunk->used += rs->length;
1132  else
1133  rs->chunk->used -= rs->length;
1134  }
1135 
1136  if (rs->chunk) {
1137  LIST_ENTRY* le2 = le->Blink;
1138 
1139  while (le2 != rollback) {
1140  LIST_ENTRY* le3 = le2->Blink;
1142 
1143  if (ri2->type == ROLLBACK_ADD_SPACE || ri2->type == ROLLBACK_SUBTRACT_SPACE) {
1144  rollback_space* rs2 = ri2->ptr;
1145 
1146  if (rs2->chunk == rs->chunk) {
1147  if (ri2->type == ROLLBACK_ADD_SPACE) {
1148  space_list_subtract2(rs2->list, rs2->list_size, rs2->address, rs2->length, NULL, NULL);
1149  rs->chunk->used += rs2->length;
1150  } else {
1151  space_list_add2(rs2->list, rs2->list_size, rs2->address, rs2->length, NULL, NULL);
1152  rs->chunk->used -= rs2->length;
1153  }
1154 
1155  ExFreePool(rs2);
1156  RemoveEntryList(&ri2->list_entry);
1157  ExFreePool(ri2);
1158  }
1159  }
1160 
1161  le2 = le3;
1162  }
1163 
1165  }
1166 
1167  ExFreePool(rs);
1168 
1169  break;
1170  }
1171  }
1172 
1173  ExFreePool(ri);
1174  }
1175 }
LIST_ENTRY * list_size
Definition: btrfs_drv.h:1199
uint8_t type
Definition: btrfs.h:340
NTSTATUS update_changed_extent_ref(device_extension *Vcb, chunk *c, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, int32_t count, bool no_csum, bool superseded, PIRP Irp)
Definition: extent-tree.c:1950
EXTENT_DATA2 * ed2
Definition: write.c:2819
enum rollback_type type
Definition: btrfs_drv.h:1218
struct _LIST_ENTRY * Blink
Definition: typedefs.h:120
FORCEINLINE PLIST_ENTRY RemoveTailList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:154
LONG NTSTATUS
Definition: precomp.h:26
release_chunk_lock(c, Vcb)
uint64_t used
Definition: btrfs_drv.h:552
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
bool ignore
Definition: btrfs_drv.h:221
uint64_t length
Definition: btrfs_drv.h:1201
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
Definition: rtlfuncs.h:105
chunk * chunk
Definition: btrfs_drv.h:1202
uint64_t address
Definition: btrfs.h:345
uint64_t address
Definition: btrfs_drv.h:1200
uint64_t offset
Definition: btrfs_drv.h:218
smooth NULL
Definition: ftsmooth.c:416
uint64_t size
Definition: btrfs.h:346
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
LIST_ENTRY list_entry
Definition: btrfs_drv.h:1220
if(!(yy_init))
Definition: macro.lex.yy.c:714
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
uint64_t inode
Definition: btrfs_drv.h:278
#define BTRFS_INODE_NODATASUM
Definition: propsheet.h:76
#define Vcb
Definition: cdprocs.h:1425
const GLubyte * c
Definition: glext.h:8905
Definition: typedefs.h:117
#define EXTENT_TYPE_PREALLOC
Definition: btrfs.h:71
INODE_ITEM inode_item
Definition: btrfs_drv.h:281
uint64_t num_bytes
Definition: btrfs.h:348
uint64_t st_blocks
Definition: btrfs.h:272
uint64_t flags
Definition: btrfs.h:279
#define EXTENT_TYPE_REGULAR
Definition: btrfs.h:70
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
uint8_t data[1]
Definition: btrfs.h:341
extent * ext
Definition: btrfs_drv.h:1207
chunk * get_chunk_from_address(device_extension *Vcb, uint64_t address)
Definition: write.c:89
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
#define acquire_chunk_lock(c, Vcb)
Definition: btrfs_drv.h:1093
struct _root * subvol
Definition: btrfs_drv.h:277
Definition: list.h:27
_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
EXTENT_DATA extent_data
Definition: btrfs_drv.h:227
LIST_ENTRY * list
Definition: btrfs_drv.h:1198
uint64_t offset
Definition: btrfs.h:347
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
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

Referenced by _Dispatch_type_(), balance_data_chunk(), balance_metadata_chunk(), check_for_orphans_root(), clear_free_space_cache(), delete_reparse_point(), do_create_snapshot(), do_write(), duplicate_extents(), load_stored_free_space_cache(), set_end_of_file_information(), set_link_information(), set_rename_information(), set_reparse_point(), set_valid_data_length_information(), set_zero_data(), and write_file().

◆ find_item()

NTSTATUS find_item ( _In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension Vcb,
_In_ root r,
_Out_ traverse_ptr tp,
_In_ const KEY searchkey,
_In_ bool  ignore,
_In_opt_ PIRP  Irp 
)

Definition at line 548 of file treefuncs.c.

549  {
551 
552  if (!r->treeholder.tree) {
553  Status = do_load_tree(Vcb, &r->treeholder, r, NULL, NULL, Irp);
554  if (!NT_SUCCESS(Status)) {
555  ERR("do_load_tree returned %08x\n", Status);
556  return Status;
557  }
558  }
559 
560  Status = find_item_in_tree(Vcb, r->treeholder.tree, tp, searchkey, ignore, 0, Irp);
562  ERR("find_item_in_tree returned %08x\n", Status);
563  }
564 
565  return Status;
566 }
_In_ PIRP Irp
Definition: csq.h:116
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
int ignore(int trapCode, ppc_trap_frame_t *trap)
Definition: mmuobject.c:296
static NTSTATUS find_item_in_tree(device_extension *Vcb, tree *t, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
Definition: treefuncs.c:443
LONG NTSTATUS
Definition: precomp.h:26
smooth NULL
Definition: ftsmooth.c:416
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
#define STATUS_NOT_FOUND
Definition: shellext.h:67
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
Definition: treefuncs.c:218

Referenced by commit_batch_list_root(), insert_tree_item(), and skip_to_difference().

◆ find_item_in_tree()

static NTSTATUS find_item_in_tree ( device_extension Vcb,
tree t,
traverse_ptr tp,
const KEY searchkey,
bool  ignore,
uint8_t  level,
PIRP  Irp 
)
static

Definition at line 443 of file treefuncs.c.

443  {
444  int cmp;
445  tree_data *td, *lasttd;
446  KEY key2;
447 
448  cmp = 1;
449  td = first_item(t);
450  lasttd = NULL;
451 
452  if (!td) return STATUS_NOT_FOUND;
453 
454  key2 = *searchkey;
455 
456  do {
457  cmp = keycmp(key2, td->key);
458 
459  if (cmp == 1) {
460  lasttd = td;
461  td = next_item(t, td);
462  }
463 
464  if (t->header.level == 0 && cmp == 0 && !ignore && td && td->ignore) {
465  tree_data* origtd = td;
466 
467  while (td && td->ignore)
468  td = next_item(t, td);
469 
470  if (td) {
471  cmp = keycmp(key2, td->key);
472 
473  if (cmp != 0) {
474  td = origtd;
475  cmp = 0;
476  }
477  } else
478  td = origtd;
479  }
480  } while (td && cmp == 1);
481 
482  if ((cmp == -1 || !td) && lasttd)
483  td = lasttd;
484 
485  if (t->header.level == 0) {
486  if (td->ignore && !ignore) {
487  traverse_ptr oldtp;
488 
489  oldtp.tree = t;
490  oldtp.item = td;
491 
492  while (find_prev_item(Vcb, &oldtp, tp, Irp)) {
493  if (!tp->item->ignore)
494  return STATUS_SUCCESS;
495 
496  oldtp = *tp;
497  }
498 
499  // if no valid entries before where item should be, look afterwards instead
500 
501  oldtp.tree = t;
502  oldtp.item = td;
503 
504  while (find_next_item(Vcb, &oldtp, tp, true, Irp)) {
505  if (!tp->item->ignore)
506  return STATUS_SUCCESS;
507 
508  oldtp = *tp;
509  }
510 
511  return STATUS_NOT_FOUND;
512  } else {
513  tp->tree = t;
514  tp->item = td;
515  }
516 
517  return STATUS_SUCCESS;
518  } else {
520 
521  while (td && td->treeholder.tree && IsListEmpty(&td->treeholder.tree->itemlist)) {
522  td = prev_item(t, td);
523  }
524 
525  if (!td)
526  return STATUS_NOT_FOUND;
527 
528  if (t->header.level <= level) {
529  tp->tree = t;
530  tp->item = td;
531  return STATUS_SUCCESS;
532  }
533 
534  if (!td->treeholder.tree) {
535  Status = do_load_tree(Vcb, &td->treeholder, t->root, t, td, Irp);
536  if (!NT_SUCCESS(Status)) {
537  ERR("do_load_tree returned %08x\n", Status);
538  return Status;
539  }
540  }
541 
542  Status = find_item_in_tree(Vcb, td->treeholder.tree, tp, searchkey, ignore, level, Irp);
543 
544  return Status;
545  }
546 }
GLint level
Definition: gl.h:1546
_In_ PIRP Irp
Definition: csq.h:116
int ignore(int trapCode, ppc_trap_frame_t *trap)
Definition: mmuobject.c:296
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
static NTSTATUS find_item_in_tree(device_extension *Vcb, tree *t, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
Definition: treefuncs.c:443
#define keycmp(key1, key2)
Definition: btrfs_drv.h:980
LONG NTSTATUS
Definition: precomp.h:26
tree_holder treeholder
Definition: btrfs_drv.h:406
GLdouble GLdouble t
Definition: gl.h:2047
#define cmp(status, error)
Definition: error.c:114
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
tree * tree
Definition: btrfs_drv.h:495
struct _tree * tree
Definition: btrfs_drv.h:396
smooth NULL
Definition: ftsmooth.c:416
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
#define STATUS_NOT_FOUND
Definition: shellext.h:67
static __inline tree_data * prev_item(tree *t, tree_data *td)
Definition: treefuncs.c:325
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
static __inline tree_data * next_item(tree *t, tree_data *td)
Definition: treefuncs.c:334
#define Vcb
Definition: cdprocs.h:1425
tree_data * item
Definition: btrfs_drv.h:496
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
bool ignore
Definition: btrfs_drv.h:402
Definition: btrfs.h:126
NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
Definition: treefuncs.c:218
return STATUS_SUCCESS
Definition: btrfs.c:2966
static __inline tree_data * first_item(tree *t)
Definition: treefuncs.c:316
bool find_prev_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *prev_tp, PIRP Irp)
Definition: treefuncs.c:698

Referenced by find_item(), and find_item_to_level().

◆ find_item_to_level()

NTSTATUS find_item_to_level ( device_extension Vcb,
root r,
traverse_ptr tp,
const KEY searchkey,
bool  ignore,
uint8_t  level,
PIRP  Irp 
)

Definition at line 568 of file treefuncs.c.

568  {
570 
571  if (!r->treeholder.tree) {
572  Status = do_load_tree(Vcb, &r->treeholder, r, NULL, NULL, Irp);
573  if (!NT_SUCCESS(Status)) {
574  ERR("do_load_tree returned %08x\n", Status);
575  return Status;
576  }
577  }
578 
579  Status = find_item_in_tree(Vcb, r->treeholder.tree, tp, searchkey, ignore, level, Irp);
581  ERR("find_item_in_tree returned %08x\n", Status);
582  }
583 
584  if (Status == STATUS_NOT_FOUND) {
585  tp->tree = r->treeholder.tree;
586  tp->item = NULL;
587  }
588 
589  return Status;
590 }
GLint level
Definition: gl.h:1546
_In_ PIRP Irp
Definition: csq.h:116
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
int ignore(int trapCode, ppc_trap_frame_t *trap)
Definition: mmuobject.c:296
static NTSTATUS find_item_in_tree(device_extension *Vcb, tree *t, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
Definition: treefuncs.c:443
LONG NTSTATUS
Definition: precomp.h:26
tree * tree
Definition: btrfs_drv.h:495
smooth NULL
Definition: ftsmooth.c:416
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
#define STATUS_NOT_FOUND
Definition: shellext.h:67
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
tree_data * item
Definition: btrfs_drv.h:496
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
Definition: treefuncs.c:218

Referenced by next_item2(), and write_metadata_items().

◆ find_next_item()

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 at line 592 of file treefuncs.c.

592  {
593  tree* t;
594  tree_data *td = NULL, *next;
596 
597  next = next_item(tp->tree, tp->item);
598 
599  if (!ignore) {
600  while (next && next->ignore)
601  next = next_item(tp->tree, next);
602  }
603 
604  if (next) {
605  next_tp->tree = tp->tree;
606  next_tp->item = next;
607 
608 #ifdef DEBUG_PARANOID
609  if (!ignore && next_tp->item->ignore) {
610  ERR("error - returning ignored item\n");
611  int3;
612  }
613 #endif
614 
615  return true;
616  }
617 
618  if (!tp->tree->parent)
619  return false;
620 
621  t = tp->tree;
622  do {
623  if (t->parent) {
624  td = next_item(t->parent, t->paritem);
625 
626  if (td) break;
627  }
628 
629  t = t->parent;
630  } while (t);
631 
632  if (!t)
633  return false;
634 
635  if (!td->treeholder.tree) {
636  Status = do_load_tree(Vcb, &td->treeholder, t->parent->root, t->parent, td, Irp);
637  if (!NT_SUCCESS(Status)) {
638  ERR("do_load_tree returned %08x\n", Status);
639  return false;
640  }
641  }
642 
643  t = td->treeholder.tree;
644 
645  while (t->header.level != 0) {
646  tree_data* fi;
647 
648  fi = first_item(t);
649 
650  if (!fi->treeholder.tree) {
651  Status = do_load_tree(Vcb, &fi->treeholder, t->parent->root, t, fi, Irp);
652  if (!NT_SUCCESS(Status)) {
653  ERR("do_load_tree returned %08x\n", Status);
654  return false;
655  }
656  }
657 
658  t = fi->treeholder.tree;
659  }
660 
661  next_tp->tree = t;
662  next_tp->item = first_item(t);
663 
664  if (!ignore && next_tp->item->ignore) {
665  traverse_ptr ntp2;
666  bool b;
667 
668  while ((b = find_next_item(Vcb, next_tp, &ntp2, true, Irp))) {
669  *next_tp = ntp2;
670 
671  if (!next_tp->item->ignore)
672  break;
673  }
674 
675  if (!b)
676  return false;
677  }
678 
679 #ifdef DEBUG_PARANOID
680  if (!ignore && next_tp->item->ignore) {
681  ERR("error - returning ignored item\n");
682  int3;
683  }
684 #endif
685 
686  return true;
687 }
_In_ PIRP Irp
Definition: csq.h:116
int ignore(int trapCode, ppc_trap_frame_t *trap)
Definition: mmuobject.c:296
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
LONG NTSTATUS
Definition: precomp.h:26
#define int3
Definition: btrfs_drv.h:1653
tree_holder treeholder
Definition: btrfs_drv.h:406
GLdouble GLdouble t
Definition: gl.h:2047
tree * tree
Definition: btrfs_drv.h:495
struct _tree * tree
Definition: btrfs_drv.h:396
smooth NULL
Definition: ftsmooth.c:416
struct _tree * parent
Definition: btrfs_drv.h:426
#define b
Definition: ke_i.h:79
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
static __inline tree_data * next_item(tree *t, tree_data *td)
Definition: treefuncs.c:334
#define Vcb
Definition: cdprocs.h:1425
tree_data * item
Definition: btrfs_drv.h:496
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
bool ignore
Definition: btrfs_drv.h:402
static unsigned __int64 next
Definition: rand_nt.c:6
NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
Definition: treefuncs.c:218
static __inline tree_data * first_item(tree *t)
Definition: treefuncs.c:316

Referenced by _Function_class_(), add_checksum_entry(), add_data_reloc(), add_metadata_reloc(), balance_data_chunk(), balance_metadata_chunk(), check_for_orphans_root(), clear_free_space_cache(), commit_batch_list_root(), convert_old_extent(), data_reloc_add_tree_edr(), find_disk_holes(), find_item_in_tree(), get_dir_last_child(), is_extent_unique(), load_chunk_root(), load_csum(), load_dir_children(), load_free_space_cache(), load_stored_free_space_tree(), log_unrecoverable_error(), look_for_roots(), open_fcb(), open_fileref_by_inode(), scrub_chunk(), scrub_chunk_raid56(), scrub_chunk_raid56_stripe_run(), trim_unalloc_space(), try_clone(), and try_clone_edr().

◆ find_prev_item()

bool find_prev_item ( _Requires_lock_held_(_Curr_->tree_lock) device_extension Vcb,
const traverse_ptr tp,
traverse_ptr prev_tp,
PIRP  Irp 
)

Definition at line 698 of file treefuncs.c.

698  {
699  tree* t;
700  tree_data* td;
702 
703  // FIXME - support ignore flag
704  if (prev_item(tp->tree, tp->item)) {
705  prev_tp->tree = tp->tree;
706  prev_tp->item = prev_item(tp->tree, tp->item);
707 
708  return true;
709  }
710 
711  if (!tp->tree->parent)
712  return false;
713 
714  t = tp->tree;
715  while (t && (!t->parent || !prev_item(t->parent, t->paritem))) {
716  t = t->parent;
717  }
718 
719  if (!t)
720  return false;
721 
722  td = prev_item(t->parent, t->paritem);
723 
724  if (!td->treeholder.tree) {
725  Status = do_load_tree(Vcb, &td->treeholder, t->parent->root, t->parent, td, Irp);
726  if (!NT_SUCCESS(Status)) {
727  ERR("do_load_tree returned %08x\n", Status);
728  return false;
729  }
730  }
731 
732  t = td->treeholder.tree;
733 
734  while (t->header.level != 0) {
735  tree_data* li;
736 
737  li = last_item(t);
738 
739  if (!li->treeholder.tree) {
740  Status = do_load_tree(Vcb, &li->treeholder, t->parent->root, t, li, Irp);
741  if (!NT_SUCCESS(Status)) {
742  ERR("do_load_tree returned %08x\n", Status);
743  return false;
744  }
745  }
746 
747  t = li->treeholder.tree;
748  }
749 
750  prev_tp->tree = t;
751  prev_tp->item = last_item(t);
752 
753  return true;
754 }
_In_ PIRP Irp
Definition: csq.h:116
LONG NTSTATUS
Definition: precomp.h:26
tree_holder treeholder
Definition: btrfs_drv.h:406
GLdouble GLdouble t
Definition: gl.h:2047
tree * tree
Definition: btrfs_drv.h:495
struct _tree * tree
Definition: btrfs_drv.h:396
static __inline tree_data * last_item(tree *t)
Definition: treefuncs.c:689
struct _tree * parent
Definition: btrfs_drv.h:426
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
static __inline tree_data * prev_item(tree *t, tree_data *td)
Definition: treefuncs.c:325
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
tree_data * item
Definition: btrfs_drv.h:496
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
Definition: treefuncs.c:218

Referenced by find_item_in_tree(), and get_last_inode().

◆ find_tree_end()

static void find_tree_end ( tree t,
KEY tree_end,
bool no_end 
)
static

Definition at line 1177 of file treefuncs.c.

1177  {
1178  tree* p;
1179 
1180  p = t;
1181  do {
1182  tree_data* pi;
1183 
1184  if (!p->parent) {
1185  *no_end = true;
1186  return;
1187  }
1188 
1189  pi = p->paritem;
1190 
1191  if (pi->list_entry.Flink != &p->parent->itemlist) {
1192  tree_data* td = CONTAINING_RECORD(pi->list_entry.Flink, tree_data, list_entry);
1193 
1194  *tree_end = td->key;
1195  *no_end = false;
1196  return;
1197  }
1198 
1199  p = p->parent;
1200  } while (p);
1201 }
GLdouble GLdouble t
Definition: gl.h:2047
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
static DWORD pi
Definition: protocol.c:150
Definition: list.h:27
GLfloat GLfloat p
Definition: glext.h:8902

Referenced by commit_batch_list_root().

◆ first_item()

static __inline tree_data* first_item ( tree t)
static

Definition at line 316 of file treefuncs.c.

316  {
317  LIST_ENTRY* le = t->itemlist.Flink;
318 
319  if (le == &t->itemlist)
320  return NULL;
321 
323 }
GLdouble GLdouble t
Definition: gl.h:2047
smooth NULL
Definition: ftsmooth.c:416
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
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
Definition: typedefs.h:117
Definition: list.h:27

Referenced by find_item_in_tree(), find_next_item(), and test_comboex().

◆ free_tree()

void free_tree ( tree t)

Definition at line 260 of file treefuncs.c.

260  {
261  tree* par;
262  root* r = t->root;
263 
264  // No need to acquire lock, as this is only ever called while Vcb->tree_lock held exclusively
265 
266  par = t->parent;
267 
268  if (r && r->treeholder.tree != t)
269  r = NULL;
270 
271  if (par) {
272  if (t->paritem)
273  t->paritem->treeholder.tree = NULL;
274  }
275 
276  while (!IsListEmpty(&t->itemlist)) {
278 
279  if (t->header.level == 0 && td->data && td->inserted)
280  ExFreePool(td->data);
281 
282  ExFreeToPagedLookasideList(&t->Vcb->tree_data_lookaside, td);
283  }
284 
285  RemoveEntryList(&t->list_entry);
286 
287  if (r)
288  r->treeholder.tree = NULL;
289 
290  if (t->list_entry_hash.Flink) {
291  uint8_t h = t->hash >> 24;
292  if (t->Vcb->trees_ptrs[h] == &t->list_entry_hash) {
293  if (t->list_entry_hash.Flink != &t->Vcb->trees_hash) {
294  tree* t2 = CONTAINING_RECORD(t->list_entry_hash.Flink, tree, list_entry_hash);
295 
296  if ((t2->hash >> 24) == h)
297  t->Vcb->trees_ptrs[h] = &t2->list_entry_hash;
298  else
299  t->Vcb->trees_ptrs[h] = NULL;
300  } else
301  t->Vcb->trees_ptrs[h] = NULL;
302  }
303 
304  RemoveEntryList(&t->list_entry_hash);
305  }
306 
307  if (t->buf)
308  ExFreePool(t->buf);
309 
310  if (t->nonpaged)
311  ExFreePool(t->nonpaged);
312 
313  ExFreePool(t);
314 }
bool inserted
Definition: btrfs_drv.h:403
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
LIST_ENTRY list_entry_hash
Definition: btrfs_drv.h:431
GLdouble GLdouble t
Definition: gl.h:2047
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
uint8_t * data
Definition: btrfs_drv.h:410
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
Definition: rtlfuncs.h:105
smooth NULL
Definition: ftsmooth.c:416
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
struct _tree * parent
Definition: btrfs_drv.h:426
uint32_t hash
Definition: btrfs_drv.h:422
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
BYTE uint8_t
Definition: msvideo1.c:66
Definition: list.h:27
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

Referenced by do_splits(), free_trees(), free_trees_root(), tree_concat(), and try_tree_amalgamate().

◆ free_trees()

void free_trees ( device_extension Vcb)

Definition at line 793 of file treefuncs.c.

793  {
794  LIST_ENTRY* le;
795  ULONG level;
796 
797  for (level = 0; level <= 255; level++) {
798  bool empty = true;
799 
800  le = Vcb->trees.Flink;
801 
802  while (le != &Vcb->trees) {
803  LIST_ENTRY* nextle = le->Flink;
805  root* r = t->root;
806 
807  if (t->header.level == level) {
808  bool top = !t->paritem;
809 
810  empty = false;
811 
812  free_tree(t);
813  if (top && r->treeholder.tree == t)
814  r->treeholder.tree = NULL;
815 
816  if (IsListEmpty(&Vcb->trees))
817  return;
818  } else if (t->header.level > level)
819  empty = false;
820 
821  le = nextle;
822  }
823 
824  if (empty)
825  break;
826  }
827 
828  reap_filerefs(Vcb, Vcb->root_fileref);
829  reap_fcbs(Vcb);
830 }
GLint level
Definition: gl.h:1546
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
static const WCHAR empty[]
Definition: main.c:49
void reap_fcbs(device_extension *Vcb)
Definition: btrfs.c:1805
GLdouble GLdouble t
Definition: gl.h:2047
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
smooth NULL
Definition: ftsmooth.c:416
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
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
void reap_filerefs(device_extension *Vcb, file_ref *fr)
Definition: btrfs.c:1875
#define Vcb
Definition: cdprocs.h:1425
Definition: typedefs.h:117
Definition: list.h:27
unsigned int ULONG
Definition: retypes.h:1
void free_tree(tree *t)
Definition: treefuncs.c:260
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859

Referenced by _Dispatch_type_(), _Function_class_(), add_balance_item(), add_device(), balance_data_chunk(), balance_metadata_chunk(), dismount_volume(), do_create_snapshot(), do_flush(), finish_removing_device(), invalidate_volumes(), lock_volume(), pnp_query_remove_device(), remove_balance_item(), and try_consolidation().

◆ free_trees_root()

void free_trees_root ( device_extension Vcb,
root r 
)

Definition at line 756 of file treefuncs.c.

756  {
757  LIST_ENTRY* le;
758  ULONG level;
759 
760  for (level = 0; level <= 255; level++) {
761  bool empty = true;
762 
763  le = Vcb->trees.Flink;
764 
765  while (le != &Vcb->trees) {
766  LIST_ENTRY* nextle = le->Flink;
768 
769  if (t->root == r) {
770  if (t->header.level == level) {
771  bool top = !t->paritem;
772 
773  empty = false;
774 
775  free_tree(t);
776  if (top && r->treeholder.tree == t)
777  r->treeholder.tree = NULL;
778 
779  if (IsListEmpty(&Vcb->trees))
780  return;
781  } else if (t->header.level > level)
782  empty = false;
783  }
784 
785  le = nextle;
786  }
787 
788  if (empty)
789  break;
790  }
791 }
GLint level
Definition: gl.h:1546
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
static const WCHAR empty[]
Definition: main.c:49
GLdouble GLdouble t
Definition: gl.h:2047
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
smooth NULL
Definition: ftsmooth.c:416
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
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define Vcb
Definition: cdprocs.h:1425
Definition: typedefs.h:117
Definition: list.h:27
unsigned int ULONG
Definition: retypes.h:1
void free_tree(tree *t)
Definition: treefuncs.c:260
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859

Referenced by drop_root().

◆ handle_batch_collision()

static NTSTATUS handle_batch_collision ( device_extension Vcb,
batch_item bi,
tree t,
tree_data td,
tree_data newtd,
LIST_ENTRY listhead,
bool ignore 
)
static

Definition at line 1267 of file treefuncs.c.

1267  {
1271  uint16_t maxlen = (uint16_t)(Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
1272 
1273  switch (bi->operation) {
1274  case Batch_SetXattr: {
1275  if (td->size < sizeof(DIR_ITEM)) {
1276  ERR("(%I64x,%x,%I64x) was %u bytes, expected at least %u\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset, td->size, sizeof(DIR_ITEM));
1277  } else {
1278  uint8_t* newdata;
1279  ULONG size = td->size;
1280  DIR_ITEM* newxa = (DIR_ITEM*)bi->data;
1281  DIR_ITEM* xa = (DIR_ITEM*)td->data;
1282 
1283  while (true) {
1284  ULONG oldxasize;
1285 
1286  if (size < sizeof(DIR_ITEM) || size < sizeof(DIR_ITEM) - 1 + xa->m + xa->n) {
1287  ERR("(%I64x,%x,%I64x) was truncated\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1288  break;
1289  }
1290 
1291  oldxasize = sizeof(DIR_ITEM) - 1 + xa->m + xa->n;
1292 
1293  if (xa->n == newxa->n && RtlCompareMemory(newxa->name, xa->name, xa->n) == xa->n) {
1294  uint64_t pos;
1295 
1296  // replace
1297 
1298  if (td->size + bi->datalen - oldxasize > maxlen)
1299  ERR("DIR_ITEM would be over maximum size, truncating (%u + %u - %u > %u)\n", td->size, bi->datalen, oldxasize, maxlen);
1300 
1301  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen - oldxasize, ALLOC_TAG);
1302  if (!newdata) {
1303  ERR("out of memory\n");
1305  }
1306 
1307  pos = (uint8_t*)xa - td->data;
1308  if (pos + oldxasize < td->size) // copy after changed xattr
1309  RtlCopyMemory(newdata + pos + bi->datalen, td->data + pos + oldxasize, (ULONG)(td->size - pos - oldxasize));
1310 
1311  if (pos > 0) { // copy before changed xattr
1312  RtlCopyMemory(newdata, td->data, (ULONG)pos);
1313  xa = (DIR_ITEM*)(newdata + pos);
1314  } else
1315  xa = (DIR_ITEM*)newdata;
1316 
1317  RtlCopyMemory(xa, bi->data, bi->datalen);
1318 
1319  bi->datalen = (uint16_t)min(td->size + bi->datalen - oldxasize, maxlen);
1320 
1321  ExFreePool(bi->data);
1322  bi->data = newdata;
1323 
1324  break;
1325  }
1326 
1327  if ((uint8_t*)xa - (uint8_t*)td->data + oldxasize >= size) {
1328  // not found, add to end of data
1329 
1330  if (td->size + bi->datalen > maxlen)
1331  ERR("DIR_ITEM would be over maximum size, truncating (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1332 
1333  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1334  if (!newdata) {
1335  ERR("out of memory\n");
1337  }
1338 
1339  RtlCopyMemory(newdata, td->data, td->size);
1340 
1341  xa = (DIR_ITEM*)((uint8_t*)newdata + td->size);
1342  RtlCopyMemory(xa, bi->data, bi->datalen);
1343 
1344  bi->datalen = min(bi->datalen + td->size, maxlen);
1345 
1346  ExFreePool(bi->data);
1347  bi->data = newdata;
1348 
1349  break;
1350  } else {
1351  xa = (DIR_ITEM*)&xa->name[xa->m + xa->n];
1352  size -= oldxasize;
1353  }
1354  }
1355  }
1356  break;
1357  }
1358 
1359  case Batch_DirItem: {
1360  uint8_t* newdata;
1361 
1362  if (td->size + bi->datalen > maxlen) {
1363  ERR("DIR_ITEM would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1364  return STATUS_INTERNAL_ERROR;
1365  }
1366 
1367  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1368  if (!newdata) {
1369  ERR("out of memory\n");
1371  }
1372 
1373  RtlCopyMemory(newdata, td->data, td->size);
1374 
1375  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1376 
1377  bi->datalen += td->size;
1378 
1379  ExFreePool(bi->data);
1380  bi->data = newdata;
1381 
1382  break;
1383  }
1384 
1385  case Batch_InodeRef: {
1386  uint8_t* newdata;
1387 
1388  if (td->size + bi->datalen > maxlen) {
1389  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1390  INODE_REF* ir = (INODE_REF*)bi->data;
1391  INODE_EXTREF* ier;
1392  uint16_t ierlen;
1393  batch_item* bi2;
1394  LIST_ENTRY* le;
1395  bool inserted = false;
1396 
1397  TRACE("INODE_REF would be too long, adding INODE_EXTREF instead\n");
1398 
1399  ierlen = (uint16_t)(offsetof(INODE_EXTREF, name[0]) + ir->n);
1400 
1401  ier = ExAllocatePoolWithTag(PagedPool, ierlen, ALLOC_TAG);
1402  if (!ier) {
1403  ERR("out of memory\n");
1405  }
1406 
1407  ier->dir = bi->key.offset;
1408  ier->index = ir->index;
1409  ier->n = ir->n;
1410  RtlCopyMemory(ier->name, ir->name, ier->n);
1411 
1412  bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
1413  if (!bi2) {
1414  ERR("out of memory\n");
1415  ExFreePool(ier);
1417  }
1418 
1419  bi2->key.obj_id = bi->key.obj_id;
1420  bi2->key.obj_type = TYPE_INODE_EXTREF;
1421  bi2->key.offset = calc_crc32c((uint32_t)ier->dir, (uint8_t*)ier->name, ier->n);
1422  bi2->data = ier;
1423  bi2->datalen = ierlen;
1424  bi2->operation = Batch_InodeExtRef;
1425 
1426  le = bi->list_entry.Flink;
1427  while (le != listhead) {
1429 
1430  if (keycmp(bi3->key, bi2->key) != -1) {
1431  InsertHeadList(le->Blink, &bi2->list_entry);
1432  inserted = true;
1433  }
1434 
1435  le = le->Flink;
1436  }
1437 
1438  if (!inserted)
1439  InsertTailList(listhead, &bi2->list_entry);
1440 
1441  *ignore = true;
1442  return STATUS_SUCCESS;
1443  } else {
1444  ERR("INODE_REF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1445  return STATUS_INTERNAL_ERROR;
1446  }
1447  }
1448 
1449  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1450  if (!newdata) {
1451  ERR("out of memory\n");
1453  }
1454 
1455  RtlCopyMemory(newdata, td->data, td->size);
1456 
1457  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1458 
1459  bi->datalen += td->size;
1460 
1461  ExFreePool(bi->data);
1462  bi->data = newdata;
1463 
1464  break;
1465  }
1466 
1467  case Batch_InodeExtRef: {
1468  uint8_t* newdata;
1469 
1470  if (td->size + bi->datalen > maxlen) {
1471  ERR("INODE_EXTREF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1472  return STATUS_INTERNAL_ERROR;
1473  }
1474 
1475  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1476  if (!newdata) {
1477  ERR("out of memory\n");
1479  }
1480 
1481  RtlCopyMemory(newdata, td->data, td->size);
1482 
1483  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1484 
1485  bi->datalen += td->size;
1486 
1487  ExFreePool(bi->data);
1488  bi->data = newdata;
1489 
1490  break;
1491  }
1492 
1493  case Batch_DeleteDirItem: {
1494  if (td->size < sizeof(DIR_ITEM)) {
1495  ERR("DIR_ITEM was %u bytes, expected at least %u\n", td->size, sizeof(DIR_ITEM));
1496  return STATUS_INTERNAL_ERROR;
1497  } else {
1498  DIR_ITEM *di, *deldi;
1499  LONG len;
1500 
1501  deldi = (DIR_ITEM*)bi->data;
1502  di = (DIR_ITEM*)td->data;
1503  len = td->size;
1504 
1505  do {
1506  if (di->m == deldi->m && di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n + di->m) == di->n + di->m) {
1507  uint16_t newlen = td->size - (sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m);
1508 
1509  if (newlen == 0) {
1510  TRACE("deleting DIR_ITEM\n");
1511  } else {
1512  uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
1513  tree_data* td2;
1514 
1515  if (!newdi) {
1516  ERR("out of memory\n");
1518  }
1519 
1520  TRACE("modifying DIR_ITEM\n");
1521 
1522  if ((uint8_t*)di > td->data) {
1523  RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
1524  dioff = newdi + ((uint8_t*)di - td->data);
1525  } else {
1526  dioff = newdi;
1527  }
1528 
1529  if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
1530  RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));
1531 
1532  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1533  if (!td2) {
1534  ERR("out of memory\n");
1535  ExFreePool(newdi);
1537  }
1538 
1539  td2->key = bi->key;
1540  td2->size = newlen;
1541  td2->data = newdi;
1542  td2->ignore = false;
1543  td2->inserted = true;
1544 
1546 
1547  t->header.num_items++;
1548  t->size += newlen + sizeof(leaf_node);
1549  t->write = true;
1550  }
1551 
1552  break;
1553  }
1554 
1555  len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
1556  di = (DIR_ITEM*)&di->name[di->n + di->m];
1557 
1558  if (len == 0) {
1559  TRACE("could not find DIR_ITEM to delete\n");
1560  *ignore = true;
1561  return STATUS_SUCCESS;
1562  }
1563  } while (len > 0);
1564  }
1565  break;
1566  }
1567 
1568  case Batch_DeleteInodeRef: {
1569  if (td->size < sizeof(INODE_REF)) {
1570  ERR("INODE_REF was %u bytes, expected at least %u\n", td->size, sizeof(INODE_REF));
1571  return STATUS_INTERNAL_ERROR;
1572  } else {
1573  INODE_REF *ir, *delir;
1574  ULONG len;
1575  bool changed = false;
1576 
1577  delir = (INODE_REF*)bi->data;
1578  ir = (INODE_REF*)td->data;
1579  len = td->size;
1580 
1581  do {
1582  uint16_t itemlen;
1583 
1584  if (len < sizeof(INODE_REF) || len < offsetof(INODE_REF, name[0]) + ir->n) {
1585  ERR("INODE_REF was truncated\n");
1586  break;
1587  }
1588 
1589  itemlen = (uint16_t)offsetof(INODE_REF, name[0]) + ir->n;
1590 
1591  if (ir->n == delir->n && RtlCompareMemory(ir->name, delir->name, ir->n) == ir->n) {
1592  uint16_t newlen = td->size - itemlen;
1593 
1594  changed = true;
1595 
1596  if (newlen == 0)
1597  TRACE("deleting INODE_REF\n");
1598  else {
1599  uint8_t *newir = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *iroff;
1600  tree_data* td2;
1601 
1602  if (!newir) {
1603  ERR("out of memory\n");
1605  }
1606 
1607  TRACE("modifying INODE_REF\n");
1608 
1609  if ((uint8_t*)ir > td->data) {
1610  RtlCopyMemory(newir, td->data, (uint8_t*)ir - td->data);
1611  iroff = newir + ((uint8_t*)ir - td->data);
1612  } else {
1613  iroff = newir;
1614  }
1615 
1616  if ((uint8_t*)&ir->name[ir->n] < td->data + td->size)
1617  RtlCopyMemory(iroff, &ir->name[ir->n], td->size - ((uint8_t*)&ir->name[ir->n] - td->data));
1618 
1619  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1620  if (!td2) {
1621  ERR("out of memory\n");
1622  ExFreePool(newir);
1624  }
1625 
1626  td2->key = bi->key;
1627  td2->size = newlen;
1628  td2->data = newir;
1629  td2->ignore = false;
1630  td2->inserted = true;
1631 
1633 
1634  t->header.num_items++;
1635  t->size += newlen + sizeof(leaf_node);
1636  t->write = true;
1637  }
1638 
1639  break;
1640  }
1641 
1642  if (len > itemlen) {
1643  len -= itemlen;
1644  ir = (INODE_REF*)&ir->name[ir->n];
1645  } else
1646  break;
1647  } while (len > 0);
1648 
1649  if (!changed) {
1650  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1651  TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1652 
1653  add_delete_inode_extref(Vcb, bi, listhead);
1654 
1655  *ignore = true;
1656  return STATUS_SUCCESS;
1657  } else
1658  WARN("entry not found in INODE_REF\n");
1659  }
1660  }
1661 
1662  break;
1663  }
1664 
1665  case Batch_DeleteInodeExtRef: {
1666  if (td->size < sizeof(INODE_EXTREF)) {
1667  ERR("INODE_EXTREF was %u bytes, expected at least %u\n", td->size, sizeof(INODE_EXTREF));
1668  return STATUS_INTERNAL_ERROR;
1669  } else {
1670  INODE_EXTREF *ier, *delier;
1671  ULONG len;
1672 
1673  delier = (INODE_EXTREF*)bi->data;
1674  ier = (INODE_EXTREF*)td->data;
1675  len = td->size;
1676 
1677  do {
1678  uint16_t itemlen;
1679 
1680  if (len < sizeof(INODE_EXTREF) || len < offsetof(INODE_EXTREF, name[0]) + ier->n) {
1681  ERR("INODE_REF was truncated\n");
1682  break;
1683  }
1684 
1685  itemlen = (uint16_t)offsetof(INODE_EXTREF, name[0]) + ier->n;
1686 
1687  if (ier->dir == delier->dir && ier->n == delier->n && RtlCompareMemory(ier->name, delier->name, ier->n) == ier->n) {
1688  uint16_t newlen = td->size - itemlen;
1689 
1690  if (newlen == 0)
1691  TRACE("deleting INODE_EXTREF\n");
1692  else {
1693  uint8_t *newier = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *ieroff;
1694  tree_data* td2;
1695 
1696  if (!newier) {
1697  ERR("out of memory\n");
1699  }
1700 
1701  TRACE("modifying INODE_EXTREF\n");
1702 
1703  if ((uint8_t*)ier > td->data) {
1704  RtlCopyMemory(newier, td->data, (uint8_t*)ier - td->data);
1705  ieroff = newier + ((uint8_t*)ier - td->data);
1706  } else {
1707  ieroff = newier;
1708  }
1709 
1710  if ((uint8_t*)&ier->name[ier->n] < td->data + td->size)
1711  RtlCopyMemory(ieroff, &ier->name[ier->n], td->size - ((uint8_t*)&ier->name[ier->n] - td->data));
1712 
1713  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1714  if (!td2) {
1715  ERR("out of memory\n");
1716  ExFreePool(newier);
1718  }
1719 
1720  td2->key = bi->key;
1721  td2->size = newlen;
1722  td2->data = newier;
1723  td2->ignore = false;
1724  td2->inserted = true;
1725 
1727 
1728  t->header.num_items++;
1729  t->size += newlen + sizeof(leaf_node);
1730  t->write = true;
1731  }
1732 
1733  break;
1734  }
1735 
1736  if (len > itemlen) {
1737  len -= itemlen;
1738  ier = (INODE_EXTREF*)&ier->name[ier->n];
1739  } else
1740  break;
1741  } while (len > 0);
1742  }
1743  break;
1744  }
1745 
1746  case Batch_DeleteXattr: {
1747  if (td->size < sizeof(DIR_ITEM)) {
1748  ERR("XATTR_ITEM was %u bytes, expected at least %u\n", td->size, sizeof(DIR_ITEM));
1749  return STATUS_INTERNAL_ERROR;
1750  } else {
1751  DIR_ITEM *di, *deldi;
1752  LONG len;
1753 
1754  deldi = (DIR_ITEM*)bi->data;
1755  di = (DIR_ITEM*)td->data;
1756  len = td->size;
1757 
1758  do {
1759  if (di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n) == di->n) {
1760  uint16_t newlen = td->size - ((uint16_t)offsetof(DIR_ITEM, name[0]) + di->n + di->m);
1761 
1762  if (newlen == 0)
1763  TRACE("deleting XATTR_ITEM\n");
1764  else {
1765  uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
1766  tree_data* td2;
1767 
1768  if (!newdi) {
1769  ERR("out of memory\n");
1771  }
1772 
1773  TRACE("modifying XATTR_ITEM\n");
1774 
1775  if ((uint8_t*)di > td->data) {
1776  RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
1777  dioff = newdi + ((uint8_t*)di - td->data);
1778  } else
1779  dioff = newdi;
1780 
1781  if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
1782  RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));
1783 
1784  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1785  if (!td2) {
1786  ERR("out of memory\n");
1787  ExFreePool(newdi);
1789  }
1790 
1791  td2->key = bi->key;
1792  td2->size = newlen;
1793  td2->data = newdi;
1794  td2->ignore = false;
1795  td2->inserted = true;
1796 
1798 
1799  t->header.num_items++;
1800  t->size += newlen + sizeof(leaf_node);
1801  t->write = true;
1802  }
1803 
1804  break;
1805  }
1806 
1807  len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
1808  di = (DIR_ITEM*)&di->name[di->n + di->m];
1809 
1810  if (len == 0) {
1811  TRACE("could not find DIR_ITEM to delete\n");
1812  *ignore = true;
1813  return STATUS_SUCCESS;
1814  }
1815  } while (len > 0);
1816  }
1817  break;
1818  }
1819 
1820  case Batch_Delete:
1821  break;
1822 
1823  default:
1824  ERR("unexpected batch operation type\n");
1825  return STATUS_INTERNAL_ERROR;
1826  }
1827 
1828  // delete old item
1829  if (!td->ignore) {
1830  td->ignore = true;
1831 
1832  t->header.num_items--;
1833  t->size -= sizeof(leaf_node) + td->size;
1834  t->write = true;
1835  }
1836 
1837  if (newtd) {
1838  newtd->data = bi->data;
1839  newtd->size = bi->datalen;
1840  InsertHeadList(td->list_entry.Blink, &newtd->list_entry);
1841  }
1842  } else {
1843  ERR("(%I64x,%x,%I64x) already exists\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1844  return STATUS_INTERNAL_ERROR;
1845  }
1846 
1847  *ignore = false;
1848  return STATUS_SUCCESS;
1849 }
LIST_ENTRY list_entry
Definition: btrfs_drv.h:485
uint64_t obj_id
Definition: btrfs.h:127
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
uint8_t obj_type
Definition: btrfs.h:128
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
uint16_t n
Definition: btrfs.h:360
bool inserted
Definition: btrfs_drv.h:403
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
#define BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF
Definition: btrfs.h:111
#define keycmp(key1, key2)
Definition: btrfs_drv.h:980
#define WARN(fmt,...)
Definition: debug.h:111
uint16_t size
Definition: btrfs_drv.h:409
enum batch_operation operation
Definition: btrfs_drv.h:484
GLdouble GLdouble t
Definition: gl.h:2047
unsigned short int uint16_t
Definition: acefiex.h:54
#define uint16_t
Definition: nsiface.idl:60
static void add_delete_inode_extref(device_extension *Vcb, batch_item *bi, LIST_ENTRY *listhead)
Definition: treefuncs.c:1219
#define InsertTailList(ListHead, Entry)
uint64_t offset
Definition: btrfs.h:129
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
void * data
Definition: btrfs_drv.h:482
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:451
#define ALLOC_TAG
Definition: btrfs_drv.h:91
LIST_ENTRY list_entry
Definition: btrfs_drv.h:401
uint16_t m
Definition: btrfs.h:257
long LONG
Definition: pedump.c:60
char name[1]
Definition: btrfs.h:354
char name[1]
Definition: btrfs.h:260
#define offsetof(TYPE, MEMBER)
uint16_t n
Definition: btrfs.h:353
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
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define TRACE(s)
Definition: solgame.cpp:4
GLsizeiptr size
Definition: glext.h:5919
if(!(yy_init))
Definition: macro.lex.yy.c:714
#define Vcb
Definition: cdprocs.h:1425
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define TYPE_INODE_EXTREF
Definition: btrfs.h:21
GLenum GLsizei len
Definition: glext.h:6722
Definition: typedefs.h:117
BYTE uint8_t
Definition: msvideo1.c:66
uint64_t dir
Definition: btrfs.h:358
char name[1]
Definition: btrfs.h:361
#define ERR(fmt,...)
Definition: debug.h:109
bool ignore
Definition: btrfs_drv.h:402
UINT64 uint64_t
Definition: types.h:77
uint64_t index
Definition: btrfs.h:352
#define min(a, b)
Definition: monoChain.cc:55
Definition: list.h:27
UINT32 uint32_t
Definition: types.h:75
Definition: name.c:36
unsigned int ULONG
Definition: retypes.h:1
uint16_t datalen
Definition: btrfs_drv.h:483
uint16_t n
Definition: btrfs.h:258
return STATUS_SUCCESS
Definition: btrfs.c:2966
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
#define RtlCompareMemory(s1, s2, l)
Definition: env_spec_w32.h:465

Referenced by commit_batch_list_root().

◆ insert_tree_item()

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 at line 857 of file treefuncs.c.

859  {
861  KEY searchkey;
862  int cmp;
863  tree_data *td, *paritem;
864  tree* t;
865 #ifdef _DEBUG
866  LIST_ENTRY* le;
867  KEY firstitem = {0xcccccccccccccccc,0xcc,0xcccccccccccccccc};
868 #endif
870 
871  TRACE("(%p, %p, %I64x, %x, %I64x, %p, %x, %p)\n", Vcb, r, obj_id, obj_type, offset, data, size, ptp);
872 
873  searchkey.obj_id = obj_id;
874  searchkey.obj_type = obj_type;
875  searchkey.offset = offset;
876 
877  Status = find_item(Vcb, r, &tp, &searchkey, true, Irp);
878  if (Status == STATUS_NOT_FOUND) {
879  if (r) {
880  if (!r->treeholder.tree) {
881  Status = do_load_tree(Vcb, &r->treeholder, r, NULL, NULL, Irp);
882  if (!NT_SUCCESS(Status)) {
883  ERR("do_load_tree returned %08x\n", Status);
884  return Status;
885  }
886  }
887 
888  if (r->treeholder.tree && r->treeholder.tree->header.num_items == 0) {
889  tp.tree = r->treeholder.tree;
890  tp.item = NULL;
891  } else {
892  ERR("error: unable to load tree for root %I64x\n", r->id);
893  return STATUS_INTERNAL_ERROR;
894  }
895  } else {
896  ERR("error: find_item returned %08x\n", Status);
897  return Status;
898  }
899  } else if (!NT_SUCCESS(Status)) {
900  ERR("find_item returned %08x\n", Status);
901  return Status;
902  }
903 
904  TRACE("tp.item = %p\n", tp.item);
905 
906  if (tp.item) {
907  TRACE("tp.item->key = %p\n", &tp.item->key);
908  cmp = keycmp(searchkey, tp.item->key);
909 
910  if (cmp == 0 && !tp.item->ignore) {
911  ERR("error: key (%I64x,%x,%I64x) already present\n", obj_id, obj_type, offset);
912 #ifdef DEBUG_PARANOID
913  int3;
914 #endif
915  return STATUS_INTERNAL_ERROR;
916  }
917  } else
918  cmp = -1;
919 
920  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
921  if (!td) {
922  ERR("out of memory\n");
924  }
925 
926  td->key = searchkey;
927  td->size = size;
928  td->data = data;
929  td->ignore = false;
930  td->inserted = true;
931 
932 #ifdef _DEBUG
933  le = tp.tree->itemlist.Flink;
934  while (le != &tp.tree->itemlist) {
936  firstitem = td2->key;
937  break;
938  }
939 
940  TRACE("inserting %I64x,%x,%I64x into tree beginning %I64x,%x,%I64x (num_items %x)\n", obj_id, obj_type, offset, firstitem.obj_id, firstitem.obj_type, firstitem.offset, tp.tree->header.num_items);
941 #endif
942 
943  if (cmp == -1) { // very first key in root
945 
946  paritem = tp.tree->paritem;
947  while (paritem) {
948  if (!keycmp(paritem->key, tp.item->key)) {
949  paritem->key = searchkey;
950  } else
951  break;
952 
953  paritem = paritem->treeholder.tree->paritem;
954  }
955  } else if (cmp == 0)
956  InsertHeadList(tp.item->list_entry.Blink, &td->list_entry); // make sure non-deleted item is before deleted ones
957  else
959 
960  tp.tree->header.num_items++;
961  tp.tree->size += size + sizeof(leaf_node);
962 
963  if (!tp.tree->write) {
964  tp.tree->write = true;
965  Vcb->need_write = true;
966  }
967 
968  if (ptp)
969  *ptp = tp;
970 
971  t = tp.tree;
972  while (t) {
973  if (t->paritem && t->paritem->ignore) {
974  t->paritem->ignore = false;
975  t->parent->header.num_items++;
976  t->parent->size += sizeof(internal_node);
977  }
978 
979  t->header.generation = Vcb->superblock.generation;
980  t = t->parent;
981  }
982 
983  return STATUS_SUCCESS;
984 }
uint64_t obj_id
Definition: btrfs.h:127
uint8_t obj_type
Definition: btrfs.h:128
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
_In_ PIRP Irp
Definition: csq.h:116
bool inserted
Definition: btrfs_drv.h:403
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
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
#define keycmp(key1, key2)
Definition: btrfs_drv.h:980
LONG NTSTATUS
Definition: precomp.h:26
#define int3
Definition: btrfs_drv.h:1653
GLintptr offset
Definition: glext.h:5920
tree_holder treeholder
Definition: btrfs_drv.h:406
uint16_t size
Definition: btrfs_drv.h:409
NTSTATUS find_item(_In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _Out_ traverse_ptr *tp, _In_ const KEY *searchkey, _In_ bool ignore, _In_opt_ PIRP Irp)
Definition: treefuncs.c:548
GLdouble GLdouble t
Definition: gl.h:2047
#define cmp(status, error)
Definition: error.c:114
uint64_t offset
Definition: btrfs.h:129
uint8_t * data
Definition: btrfs_drv.h:410
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:451
LIST_ENTRY list_entry
Definition: btrfs_drv.h:401
tree * tree
Definition: btrfs_drv.h:495
struct _tree * tree
Definition: btrfs_drv.h:396
tree_data * paritem
Definition: btrfs_drv.h:427
smooth NULL
Definition: ftsmooth.c:416
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
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define STATUS_NOT_FOUND
Definition: shellext.h:67
#define TRACE(s)
Definition: solgame.cpp:4
GLsizeiptr size
Definition: glext.h:5919
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
LIST_ENTRY itemlist
Definition: btrfs_drv.h:429
#define Vcb
Definition: cdprocs.h:1425
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
tree_data * item
Definition: btrfs_drv.h:496
tree_header header
Definition: btrfs_drv.h:421
Definition: typedefs.h:117
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
bool ignore
Definition: btrfs_drv.h:402
uint32_t size
Definition: btrfs_drv.h:424
Definition: btrfs.h:126
Definition: list.h:27
NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
Definition: treefuncs.c:218
uint32_t num_items
Definition: btrfs.h:144
return STATUS_SUCCESS
Definition: btrfs.c:2966
bool write
Definition: btrfs_drv.h:435

Referenced by add_balance_item(), add_checksum_entry(), add_data_reloc_extent_item(), add_device(), add_metadata_reloc_extent_item(), add_parents(), add_root_item_to_cache(), add_root_ref(), allocate_cache_chunk(), construct_extent_item(), create_chunk(), create_root(), create_subvol(), decrease_extent_refcount(), delete_root_ref(), do_create_snapshot(), drop_chunk(), drop_root(), flush_changed_dev_stats(), flush_changed_extent(), flush_fcb(), flush_subvol(), increase_extent_refcount(), insert_tree_extent(), insert_tree_extent_skinny(), look_for_roots(), update_chunk_usage(), update_dev_item(), update_extent_level(), update_root_backref(), and write_metadata_items().

◆ last_item()

static __inline tree_data* last_item ( tree t)
static

Definition at line 689 of file treefuncs.c.

689  {
690  LIST_ENTRY* le = t->itemlist.Blink;
691 
692  if (le == &t->itemlist)
693  return NULL;
694 
696 }
struct _LIST_ENTRY * Blink
Definition: typedefs.h:120
GLdouble GLdouble t
Definition: gl.h:2047
smooth NULL
Definition: ftsmooth.c:416
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
Definition: typedefs.h:117
Definition: list.h:27

Referenced by ext4_xattr_insert_item_ordered(), and find_prev_item().

◆ load_tree()

NTSTATUS load_tree ( device_extension Vcb,
uint64_t  addr,
uint8_t buf,
root r,
tree **  pt 
)

Definition at line 20 of file treefuncs.c.

20  {
21  tree_header* th;
22  tree* t;
23  tree_data* td;
24  uint8_t h;
25  bool inserted;
26  LIST_ENTRY* le;
27 
28  th = (tree_header*)buf;
29 
31  if (!t) {
32  ERR("out of memory\n");
34  }
35 
36  if (th->level > 0) {
38  if (!t->nonpaged) {
39  ERR("out of memory\n");
40  ExFreePool(t);
42  }
43 
44  ExInitializeFastMutex(&t->nonpaged->mutex);
45  } else
46  t->nonpaged = NULL;
47 
48  RtlCopyMemory(&t->header, th, sizeof(tree_header));
49  t->hash = calc_crc32c(0xffffffff, (uint8_t*)&addr, sizeof(uint64_t));
50  t->has_address = true;
51  t->Vcb = Vcb;
52  t->parent = NULL;
53  t->root = r;
54  t->paritem = NULL;
55  t->size = 0;
56  t->new_address = 0;
57  t->has_new_address = false;
58  t->updated_extents = false;
59  t->write = false;
60  t->uniqueness_determined = false;
61 
62  InitializeListHead(&t->itemlist);
63 
64  if (t->header.level == 0) { // leaf node
65  leaf_node* ln = (leaf_node*)(buf + sizeof(tree_header));
66  unsigned int i;
67 
68  if ((t->header.num_items * sizeof(leaf_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
69  ERR("tree at %I64x has more items than expected (%x)\n", t->header.num_items);
70  ExFreePool(t);
72  }
73 
74  for (i = 0; i < t->header.num_items; i++) {
75  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
76  if (!td) {
77  ERR("out of memory\n");
78  ExFreePool(t);
80  }
81 
82  td->key = ln[i].key;
83 
84  if (ln[i].size > 0)
85  td->data = buf + sizeof(tree_header) + ln[i].offset;
86  else
87  td->data = NULL;
88 
89  if (ln[i].size + sizeof(tree_header) + sizeof(leaf_node) > Vcb->superblock.node_size) {
90  ERR("overlarge item in tree %I64x: %u > %u\n", addr, ln[i].size, Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
91  ExFreeToPagedLookasideList(&t->Vcb->tree_data_lookaside, td);
92  ExFreePool(t);
93  return STATUS_INTERNAL_ERROR;
94  }
95 
96  td->size = (uint16_t)ln[i].size;
97  td->ignore = false;
98  td->inserted = false;
99 
100  InsertTailList(&t->itemlist, &td->list_entry);
101 
102  t->size += ln[i].size;
103  }
104 
105  t->size += t->header.num_items * sizeof(leaf_node);
106  t->buf = buf;
107  } else {
108  internal_node* in = (internal_node*)(buf + sizeof(tree_header));
109  unsigned int i;
110 
111  if ((t->header.num_items * sizeof(internal_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
112  ERR("tree at %I64x has more items than expected (%x)\n", t->header.num_items);
113  ExFreePool(t);
115  }
116 
117  for (i = 0; i < t->header.num_items; i++) {
118  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
119  if (!td) {
120  ERR("out of memory\n");
121  ExFreePool(t);
123  }
124 
125  td->key = in[i].key;
126 
127  td->treeholder.address = in[i].address;
128  td->treeholder.generation = in[i].generation;
129  td->treeholder.tree = NULL;
130  td->ignore = false;
131  td->inserted = false;
132 
133  InsertTailList(&t->itemlist, &td->list_entry);
134  }
135 
136  t->size = t->header.num_items * sizeof(internal_node);
137  t->buf = NULL;
138  }
139 
140  ExAcquireFastMutex(&Vcb->trees_list_mutex);
141 
142  InsertTailList(&Vcb->trees, &t->list_entry);
143 
144  h = t->hash >> 24;
145 
146  if (!Vcb->trees_ptrs[h]) {
147  uint8_t h2 = h;
148 
149  le = Vcb->trees_hash.Flink;
150 
151  if (h2 > 0) {
152  h2--;
153  do {
154  if (Vcb->trees_ptrs[h2]) {
155  le = Vcb->trees_ptrs[h2];
156  break;
157  }
158 
159  h2--;
160  } while (h2 > 0);
161  }
162  } else
163  le = Vcb->trees_ptrs[h];
164 
165  inserted = false;
166  while (le != &Vcb->trees_hash) {
167  tree* t2 = CONTAINING_RECORD(le, tree, list_entry_hash);
168 
169  if (t2->hash >= t->hash) {
170  InsertHeadList(le->Blink, &t->list_entry_hash);
171  inserted = true;
172  break;
173  }
174 
175  le = le->Flink;
176  }
177 
178  if (!inserted)
179  InsertTailList(&Vcb->trees_hash, &t->list_entry_hash);
180 
181  if (!Vcb->trees_ptrs[h] || t->list_entry_hash.Flink == Vcb->trees_ptrs[h])
182  Vcb->trees_ptrs[h] = &t->list_entry_hash;
183 
184  ExReleaseFastMutex(&Vcb->trees_list_mutex);
185 
186  TRACE("returning %p\n", t);
187 
188  *pt = t;
189 
190  return STATUS_SUCCESS;
191 }
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
#define pt(x, y)
Definition: drawing.c:79
bool inserted
Definition: btrfs_drv.h:403
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
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
GLintptr offset
Definition: glext.h:5920
tree_holder treeholder
Definition: btrfs_drv.h:406
uint16_t size
Definition: btrfs_drv.h:409
GLdouble GLdouble t
Definition: gl.h:2047
#define uint16_t
Definition: nsiface.idl:60
#define InsertTailList(ListHead, Entry)
VOID FASTCALL ExReleaseFastMutex(IN PFAST_MUTEX FastMutex)
Definition: fmutex.c:31
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
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:451
#define ALLOC_TAG
Definition: btrfs_drv.h:91
LIST_ENTRY list_entry
Definition: btrfs_drv.h:401
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
struct _tree * tree
Definition: btrfs_drv.h:396
smooth NULL
Definition: ftsmooth.c:416
uint32_t size
Definition: btrfs.h:151
uint32_t hash
Definition: btrfs_drv.h:422
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
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
#define TRACE(s)
Definition: solgame.cpp:4
GLsizeiptr size
Definition: glext.h:5919
FORCEINLINE VOID ExInitializeFastMutex(_Out_ PFAST_MUTEX FastMutex)
Definition: exfuncs.h:274
#define Vcb
Definition: cdprocs.h:1425
uint8_t level
Definition: btrfs.h:145
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
GLenum const GLvoid * addr
Definition: glext.h:9621
Definition: typedefs.h:117
BYTE uint8_t
Definition: msvideo1.c:66
#define ERR(fmt,...)
Definition: debug.h:109
bool ignore
Definition: btrfs_drv.h:402
UINT64 uint64_t
Definition: types.h:77
GLuint in
Definition: glext.h:9616
VOID FASTCALL ExAcquireFastMutex(IN PFAST_MUTEX FastMutex)
Definition: fmutex.c:23
KEY key
Definition: btrfs.h:149
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
uint64_t address
Definition: btrfs_drv.h:394
return STATUS_SUCCESS
Definition: btrfs.c:2966
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
uint64_t generation
Definition: btrfs_drv.h:395

Referenced by do_load_tree2(), and remove_root_extents().

◆ next_item()

static __inline tree_data* next_item ( tree t,
tree_data td 
)
static

Definition at line 334 of file treefuncs.c.

334  {
335  LIST_ENTRY* le = td->list_entry.Flink;
336 
337  if (le == &t->itemlist)
338  return NULL;
339 
341 }
GLdouble GLdouble t
Definition: gl.h:2047
LIST_ENTRY list_entry
Definition: btrfs_drv.h:401
smooth NULL
Definition: ftsmooth.c:416
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
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
Definition: typedefs.h:117
Definition: list.h:27

Referenced by ext4_fs_xattr_iterate(), ext4_xattr_purge_items(), find_item_in_tree(), find_next_item(), ME_RunOfsFromCharOfs(), next_item2(), and TREEVIEW_GetListItem().

◆ next_item2()

static NTSTATUS next_item2 ( device_extension Vcb,
tree t,
tree_data td,
traverse_ptr tp 
)
static

Definition at line 343 of file treefuncs.c.

343  {
344  tree_data* td2 = next_item(t, td);
345  tree* t2;
346 
347  if (td2) {
348  tp->tree = t;
349  tp->item = td2;
350  return STATUS_SUCCESS;
351  }
352 
353  t2 = t;
354 
355  do {
356  td2 = t2->paritem;
357  t2 = t2->parent;
358  } while (td2 && !next_item(t2, td2));
359 
360  if (!td2)
361  return STATUS_NOT_FOUND;
362 
363  td2 = next_item(t2, td2);
364 
365  return find_item_to_level(Vcb, t2->root, tp, &td2->key, false, t->header.level, NULL);
366 }
struct _root * root
Definition: btrfs_drv.h:428
GLdouble GLdouble t
Definition: gl.h:2047
tree * tree
Definition: btrfs_drv.h:495
tree_data * paritem
Definition: btrfs_drv.h:427
smooth NULL
Definition: ftsmooth.c:416
struct _tree * parent
Definition: btrfs_drv.h:426
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
#define STATUS_NOT_FOUND
Definition: shellext.h:67
static __inline tree_data * next_item(tree *t, tree_data *td)
Definition: treefuncs.c:334
#define Vcb
Definition: cdprocs.h:1425
tree_data * item
Definition: btrfs_drv.h:496
NTSTATUS find_item_to_level(device_extension *Vcb, root *r, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
Definition: treefuncs.c:568
return STATUS_SUCCESS
Definition: btrfs.c:2966

Referenced by skip_to_difference().

◆ prev_item()

static __inline tree_data* prev_item ( tree t,
tree_data td 
)
static

Definition at line 325 of file treefuncs.c.

325  {
326  LIST_ENTRY* le = td->list_entry.Blink;
327 
328  if (le == &t->itemlist)
329  return NULL;
330 
332 }
struct _LIST_ENTRY * Blink
Definition: typedefs.h:120
GLdouble GLdouble t
Definition: gl.h:2047
LIST_ENTRY list_entry
Definition: btrfs_drv.h:401
smooth NULL
Definition: ftsmooth.c:416
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
Definition: typedefs.h:117
Definition: list.h:27

Referenced by find_item_in_tree(), and find_prev_item().

◆ skip_to_difference()

NTSTATUS skip_to_difference ( device_extension Vcb,
traverse_ptr tp,
traverse_ptr tp2,
bool ended1,
bool ended2 
)

Definition at line 368 of file treefuncs.c.

368  {
370  tree *t1, *t2;
371  tree_data *td1, *td2;
372 
373  t1 = tp->tree;
374  t2 = tp2->tree;
375 
376  do {
377  td1 = t1->paritem;
378  td2 = t2->paritem;
379  t1 = t1->parent;
380  t2 = t2->parent;
381  } while (t1 && t2 && t1->header.address == t2->header.address);
382 
383  while (true) {
384  traverse_ptr tp3, tp4;
385 
386  Status = next_item2(Vcb, t1, td1, &tp3);
387  if (Status == STATUS_NOT_FOUND)
388  *ended1 = true;
389  else if (!NT_SUCCESS(Status)) {
390  ERR("next_item2 returned %08x\n", Status);
391  return Status;
392  }
393 
394  Status = next_item2(Vcb, t2, td2, &tp4);
395  if (Status == STATUS_NOT_FOUND)
396  *ended2 = true;
397  else if (!NT_SUCCESS(Status)) {
398  ERR("next_item2 returned %08x\n", Status);
399  return Status;
400  }
401 
402  if (*ended1 || *ended2) {
403  if (!*ended1) {
404  Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
405  if (!NT_SUCCESS(Status)) {
406  ERR("find_item returned %08x\n", Status);
407  return Status;
408  }
409  } else if (!*ended2) {
410  Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
411  if (!NT_SUCCESS(Status)) {
412  ERR("find_item returned %08x\n", Status);
413  return Status;
414  }
415  }
416 
417  return STATUS_SUCCESS;
418  }
419 
420  if (tp3.tree->header.address != tp4.tree->header.address) {
421  Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
422  if (!NT_SUCCESS(Status)) {
423  ERR("find_item returned %08x\n", Status);
424  return Status;
425  }
426 
427  Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
428  if (!NT_SUCCESS(Status)) {
429  ERR("find_item returned %08x\n", Status);
430  return Status;
431  }
432 
433  return STATUS_SUCCESS;
434  }
435 
436  t1 = tp3.tree;
437  td1 = tp3.item;
438  t2 = tp4.tree;
439  td2 = tp4.item;
440  }
441 }
struct _root * root
Definition: btrfs_drv.h:428
static NTSTATUS next_item2(device_extension *Vcb, tree *t, tree_data *td, traverse_ptr *tp)
Definition: treefuncs.c:343
LONG NTSTATUS
Definition: precomp.h:26
NTSTATUS find_item(_In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _Out_ traverse_ptr *tp, _In_ const KEY *searchkey, _In_ bool ignore, _In_opt_ PIRP Irp)
Definition: treefuncs.c:548
uint64_t address
Definition: btrfs.h:139
tree * tree
Definition: btrfs_drv.h:495
tree_data * paritem
Definition: btrfs_drv.h:427
smooth NULL
Definition: ftsmooth.c:416
struct _tree * parent
Definition: btrfs_drv.h:426
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2883
#define STATUS_NOT_FOUND
Definition: shellext.h:67
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define Vcb
Definition: cdprocs.h:1425
tree_data * item
Definition: btrfs_drv.h:496
tree_header header
Definition: btrfs_drv.h:421
Status
Definition: gdiplustypes.h:24
#define ERR(fmt,...)
Definition: debug.h:109
return STATUS_SUCCESS
Definition: btrfs.c:2966

Referenced by _Function_class_().