| /linux/fs/btrfs/ |
| H A D | extent-io-tree.c | 1 // SPDX-License-Identifier: GPL-2.0
8 #include "extent-io-tree.h"
15 return !RB_EMPTY_NODE(&state->rb_node); in extent_state_in_tree()
27 list_add(&state->leak_list, &states); in btrfs_leak_debug_add_state()
36 list_del(&state->leak_list); in btrfs_leak_debug_del_state()
46 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n", in btrfs_extent_state_leak_debug_check()
47 state->start, state->end, state->state, in btrfs_extent_state_leak_debug_check()
49 refcount_read(&state->refs)); in btrfs_extent_state_leak_debug_check()
50 list_del(&state->leak_list); in btrfs_extent_state_leak_debug_check()
56 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
[all …]
|
| H A D | extent_map.c | 1 // SPDX-License-Identifier: GPL-2.0
11 #include "disk-io.h"
21 return -ENOMEM; in extent_map_init()
31 * Initialize the extent tree @tree. Should be called for each new inode or
34 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument
36 tree->root = RB_ROOT; in extent_map_tree_init()
37 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
38 rwlock_init(&tree->lock); in extent_map_tree_init()
51 RB_CLEAR_NODE(&em->rb_node); in alloc_extent_map()
52 refcount_set(&em->refs, 1); in alloc_extent_map()
[all …]
|
| /linux/Documentation/core-api/ |
| H A D | maple_tree.rst | 1 .. SPDX-License-Identifier: GPL-2.0+
5 Maple Tree
13 The Maple Tree is a B-Tree data type which is optimized for storing
14 non-overlapping ranges, including ranges of size 1. The tree was designed to
17 entry in a cache-efficient manner. The tree can also be put into an RCU-safe
22 The Maple Tree maintains a small memory footprint and was designed to use
24 use the normal API. An :ref:`maple-tree-advanced-api` exists for more complex
25 scenarios. The most important usage of the Maple Tree is the tracking of the
28 The Maple Tree can store values between ``0`` and ``ULONG_MAX``. The Maple
29 Tree reserves values with the bottom two bits set to '10' which are below 4096
[all …]
|
| /linux/include/linux/ |
| H A D | rbtree.h | 1 /* SPDX-License-Identifier: GPL-2.0-or-later */
11 I know it's not the cleaner way, but in C (not in C++) to get
14 See Documentation/core-api/rbtree.rst for documentation and samples.
26 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
30 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
32 /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
34 ((node)->__rb_parent_color == (unsigned long)(node))
36 ((node)->__rb_parent_color = (unsigned long)(node))
43 /* Find logical next and previous nodes in a tree */
49 /* Postorder iteration - always visit the parent after its children */
[all …]
|
| H A D | radix-tree.h | 1 /* SPDX-License-Identifier: GPL-2.0-or-later */
31 /* nodes->parent points to next preallocated node */
37 * The bottom two bits of the slot determine how the remaining bits in the
40 * 00 - data pointer
41 * 10 - internal entry
42 * x1 - value entry
44 * The internal entry may be a pointer to the next level in the tree, a
45 * sibling entry, or an indicator that the entry in this slot has been moved
46 * to another location in the tree and the lookup should be restarted. While
47 * NULL fits the 'data pointer' pattern, it means that there is no entry in
[all …]
|
| /linux/rust/kernel/ |
| H A D | rbtree.rs | 1 // SPDX-License-Identifier: GPL-2.0
3 //! Red-black trees.
7 //! Reference: <https://docs.kernel.org/core-api/rbtree.html>
17 /// A red-black tree with owned nodes.
19 /// It is backed by the kernel C red-black trees.
23 /// In the example below we do several operations on a tree
725 tree: &'a mut RBTree<K, V>, global() field
[all...] |
| /linux/Documentation/devicetree/ |
| H A D | of_unittest.rst | 1 .. SPDX-License-Identifier: GPL-2.0
13 is attached to the live tree dynamically, independent of the machine's
18 (1) Documentation/devicetree/usage-model.rst
23 from the unflattened device tree data structure. This interface is used by
24 most of the device drivers in various use cases.
41 The EXPECT messages result in very noisy console messages that are difficult
45 from 'scripts/dtc/of_unittest_expect --help'.
48 3. Test-data
51 The Device Tree Source file (drivers/of/unittest-data/testcases.dts) contains
52 the test data required for executing the unit tests automated in
[all …]
|
| H A D | usage-model.rst | 1 .. SPDX-License-Identifier: GPL-2.0
7 The Linux usage model for device tree data
11 This article describes how Linux uses the device tree. An overview of
12 the device tree data format can be found on the device tree usage page
17 The "Open Firmware Device Tree", or simply Devicetree (DT), is a data
23 Structurally, the DT is a tree, or acyclic graph with named nodes, and
26 links from one node to another outside of the natural tree structure.
29 is defined for how data should appear in the tree to describe typical
41 already being enumerated in existing systems.
44 ----------
[all …]
|
| /linux/scripts/dtc/libfdt/ |
| H A D | libfdt.h | 1 /* SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause) */
5 * libfdt - Flat Device Tree manipulation
28 * tree, but its buffer did not have sufficient space to
29 * contain the expanded tree. Use fdt_open_into() to move the
30 * device tree to a buffer with more space. */
35 * offset which is out-of-bounds, or which points to an
44 * length, or the phandle value was either 0 or -1, which are
48 * tree created by the sequential-write functions, which is
51 /* Error codes: codes for bad device tree blobs */
53 /* FDT_ERR_TRUNCATED: FDT or a sub-block is improperly
[all …]
|
| H A D | fdt_overlay.c | 1 // SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause)
3 * libfdt - Flat Device Tree manipulation
15 * overlay_get_target_phandle - retrieves the target phandle of a fragment
16 * @fdto: pointer to the device tree overlay blob
17 * @fragment: node offset of the fragment in the overlay
21 * property) instead of a path (target-path property).
26 * -1, if the phandle was malformed
37 if ((len != sizeof(*val)) || (fdt32_to_cpu(*val) == (uint32_t)-1)) in overlay_get_target_phandle()
38 return (uint32_t)-1; in overlay_get_target_phandle()
52 if (phandle == (uint32_t)-1) in fdt_overlay_target_offset()
[all …]
|
| H A D | libfdt_internal.h | 1 /* SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause) */
5 * libfdt - Flat Device Tree manipulation
10 #define FDT_ALIGN(x, a) (((x) + (a) - 1) & ~((a) - 1))
50 * Internal helpers to access tructural elements of the device tree
54 * where unaligned memory reads will be handled in a graceful manner.
83 * You should have another method of validating the device tree, such as a
91 * This does essentially no checks. Only the latest device-tree
92 * version is correctly handled. Inconsistencies or errors in the device
93 * tree may cause undefined behaviour or crashes. Invalid parameters
96 * If an error occurs when modifying the tree it may leave the tree in
[all …]
|
| /linux/lib/zlib_deflate/ |
| H A D | deftree.c | 2 /* trees.c -- output deflated data using Huffman coding
3 * Copyright (C) 1995-1996 Jean-loup Gailly
4 * For conditions of distribution and use, see copyright notice in zlib.h
13 * Each code tree is stored in a compressed form which is itself
14 * a Huffman encoding of the lengths of all the code strings (in
16 * reconstructed from the lengths in the inflate process, as described
17 * in the deflate specification.
22 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
25 * Data Compression: Methods and Theory, pp. 49-50.
26 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
[all …]
|
| /linux/tools/include/linux/ |
| H A D | rbtree.h | 1 /* SPDX-License-Identifier: GPL-2.0-or-later */
11 I know it's not the cleaner way, but in C (not in C++) to get
14 See Documentation/core-api/rbtree.rst for documentation and samples.
34 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
39 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
41 /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
43 ((node)->__rb_parent_color == (unsigned long)(node))
45 ((node)->__rb_parent_color = (unsigned long)(node))
52 /* Find logical next and previous nodes in a tree */
58 /* Postorder iteration - always visit the parent after its children */
[all …]
|
| /linux/drivers/gpu/drm/amd/display/dc/mpc/dcn10/ |
| H A D | dcn10_mpc.c | 2 * Copyright 2012-15 Advanced Micro Devices, Inc.
6 * to deal in the Software without restriction, including without limitation
11 * The above copyright notice and this permission notice shall be included in
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
30 mpc10->mpc_regs->reg
33 mpc10->base.ctx
37 mpc10->mpc_shift->field_name, mpc10->mpc_mask->field_name
[all …]
|
| /linux/Documentation/arch/powerpc/ |
| H A D | bootwrapper.rst | 12 The boot wrapper can be found in the arch/powerpc/boot/ directory. The
13 Makefile in that directory has targets for all the available image types.
17 others. U-Boot is typically found on embedded PowerPC hardware, but there
21 The boot wrapper is built from the makefile in arch/powerpc/boot/Makefile and
23 image. The details of the build system is discussed in the next section.
28 U-Boot (for versions that don't understand the device
29 tree). This image embeds a device tree blob inside
30 the image. The boot wrapper, kernel and device tree
31 are all embedded inside the U-Boot uImage file format
34 tree before jumping into the kernel.
[all …]
|
| /linux/block/ |
| H A D | bfq-wf2q.c | 1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Hierarchical Budget Worst-case Fair Weighted Fair Queueing
4 * (B-WF2Q+): hierarchical scheduling algorithm by which the BFQ I/O
9 #include "bfq-iosched.h"
12 * bfq_gt - compare two timestamps.
20 return (s64)(a - b) > 0; in bfq_gt()
23 static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree) in bfq_root_active_entity() argument
25 struct rb_node *node = tree->rb_node; in bfq_root_active_entity()
34 return bfqq ? bfqq->ioprio_class - 1 : in bfq_class_idx()
35 BFQ_DEFAULT_GRP_CLASS - 1; in bfq_class_idx()
[all …]
|
| /linux/drivers/gpu/drm/amd/display/dc/inc/hw/ |
| H A D | mpc.h | 2 * Copyright 2012-15 Advanced Micro Devices, Inc.
6 * to deal in the Software without restriction, including without limitation
11 * The above copyright notice and this permission notice shall be included in
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
29 * Multiple Pipe/Plane Combiner (MPC) is a component in the hardware pipeline
30 * that performs blending of multiple planes, using global and per-pixel alpha.
31 * It also performs post-blending color correction operations according to the
[all …]
|
| /linux/lib/ |
| H A D | radix-tree.c | 1 // SPDX-License-Identifier: GPL-2.0-or-later
24 #include <linux/radix-tree.h>
30 #include "radix-tree.h"
33 * Radix tree node cache.
38 * The radix tree is variable-height, so an insert operation not only has
43 * The worst case is a zero height tree with just a single item at index 0,
48 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
51 * The IDR does not have to be as high as the radix tree since it uses
54 #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)
57 #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
[all …]
|
| H A D | Kconfig | 1 # SPDX-License-Identifier: GPL-2.0-only
31 converting bitfields between a CPU-usable representation and a
33 - Is little endian (bytes are reversed within a 32-bit group)
34 - The least-significant 32-bit word comes first (within a 64-bit
36 - The most significant bit of a byte is at its right (bit 0 of a
39 in the data sheets of the peripherals they are in control of.
41 When in doubt, say N.
50 For more information on KUnit and unit tests in general,
51 please refer to the KUnit documentation in Documentation/dev-tools/kunit/.
53 When in doubt, say N.
[all …]
|
| /linux/Documentation/filesystems/ext4/ |
| H A D | ifork.rst | 1 .. SPDX-License-Identifier: GPL-2.0
4 ------------------------------
7 storage in ``inode.i_block`` can be used in different ways. In general,
14 The target of a symbolic link will be stored in this field if the target
21 In ext2/3, file block numbers were mapped to logical block numbers by
22 means of an (up to) three level 1-1 block map. To find the logical block
43 Extent Tree
46 In ext4, the file to logical block map has been replaced with an extent
47 tree. Under the old scheme, allocating a contiguous run of 1,000 blocks
51 very large files with a single extent, at a considerable reduction in
[all …]
|
| /linux/fs/ext4/ |
| H A D | extents_status.c | 1 // SPDX-License-Identifier: GPL-2.0
11 * Ext4 extents status tree core functions.
21 * According to previous discussion in Ext4 Developer Workshop, we
22 * will introduce a new structure called io tree to track all extent
23 * status in order to solve some problems that we have met
24 * (e.g. Reservation space warning), and provide extent-level locking.
25 * Delay extent tree is the first step to achieve this goal. It is
27 * extent tree, whose goal is only track delayed extents in memory to
30 * delay extent tree at the first commit. But for better understand
31 * what it does, it has been rename to extent status tree.
[all …]
|
| /linux/net/sched/ |
| H A D | ematch.c | 1 // SPDX-License-Identifier: GPL-2.0-or-later
18 * causing the current position in the sequence to be pushed onto a stack
20 * in the special ematch. Matching continues in the new sequence until a
26 * ------->-PUSH-------
27 * -->-- / -->-- \ -->--
29 * +-------+-------+-------+-------+-------+--------+
31 * +-------+-------+-------+-------+-------+--------+
33 * --------<-POP---------
39 * How to write an ematch in 60 seconds
40 * ------------------------------------
[all …]
|
| /linux/fs/jfs/ |
| H A D | jfs_dmap.h | 1 /* SPDX-License-Identifier: GPL-2.0-or-later */
3 * Copyright (C) International Business Machines Corp., 2000-2002
11 #define TREESIZE (256+64+16+4+1) /* size of a dmap tree */
12 #define LEAFIND (64+16+4+1) /* index of 1st leaf of a dmap tree */
13 #define LPERDMAP 256 /* num leaves per dmap tree */
14 #define L2LPERDMAP 8 /* l2 number of leaves per dmap tree */
17 #define BUDMIN L2DBWORD /* max free string in a map word */
20 #define CTLTREESIZE (1024+256+64+16+4+1) /* size of a dmapctl tree */
21 #define CTLLEAFIND (256+64+16+4+1) /* idx of 1st leaf of a dmapctl tree */
22 #define LPERCTL 1024 /* num of leaves per dmapctl tree */
[all …]
|
| /linux/kernel/ |
| H A D | audit_tree.c | 1 // SPDX-License-Identifier: GPL-2.0
54 * audit_tree_group->mark_mutex. Thus as long as we hold
55 * audit_tree_group->mark_mutex and check that the mark is alive by
61 * the same tree.
63 * time and used in AUDIT_TREE rule matching.
68 * tree.chunks anchors chunk.owners[].list hash_lock
69 * tree.rules anchors rule.rlist audit_filter_mutex
70 * chunk.trees anchors tree
95 struct audit_tree *tree; alloc_tree() local
111 get_tree(struct audit_tree * tree) get_tree() argument
116 put_tree(struct audit_tree * tree) put_tree() argument
123 audit_tree_path(struct audit_tree * tree) audit_tree_path() argument
261 audit_tree_match(struct audit_chunk * chunk,struct audit_tree * tree) audit_tree_match() argument
397 create_chunk(struct inode * inode,struct audit_tree * tree) create_chunk() argument
458 tag_chunk(struct inode * inode,struct audit_tree * tree) tag_chunk() argument
542 kill_rules(struct audit_context * context,struct audit_tree * tree) kill_rules() argument
609 trim_marked(struct audit_tree * tree) trim_marked() argument
649 struct audit_tree *tree; audit_remove_tree_rule() local
684 struct audit_tree *tree; audit_trim_trees() local
740 audit_put_tree(struct audit_tree * tree) audit_put_tree() argument
802 struct audit_tree *seed = rule->tree, *tree; audit_add_tree_rule() local
897 struct audit_tree *tree; audit_tag_tree() local
934 struct audit_tree *tree; audit_tag_tree() local
[all...] |
| /linux/scripts/tracing/ |
| H A D | draw_functrace.py | 2 # SPDX-License-Identifier: GPL-2.0-only
7 This script parses a trace provided by the function tracer in
9 The resulted trace is processed into a tree to produce a more human
10 view of the call stack by drawing textual but hierarchical tree of
15 # mount -t tracefs nodev /sys/kernel/tracing
21 Then you have your drawn trace in draw_functrace
28 """ This class provides a tree representation of the functions
29 call stack. If a function has no parent in the kernel (interrupt,
46 into the tree at the appropriate place.
59 tree = self
[all …]
|