From 0c1bc6b84525b96aa9fb8f6fbe8c5cb26a5c0ead Mon Sep 17 00:00:00 2001 From: Mauro Carvalho Chehab Date: Tue, 14 Apr 2020 18:48:37 +0200 Subject: docs: filesystems: fix renamed references Some filesystem references got broken by a previous patch series I submitted. Address those. Signed-off-by: Mauro Carvalho Chehab Acked-by: David Sterba # fs/affs/Kconfig Link: https://lore.kernel.org/r/57318c53008dbda7f6f4a5a9e5787f4d37e8565a.1586881715.git.mchehab+huawei@kernel.org Signed-off-by: Jonathan Corbet --- lib/kobject.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/kobject.c b/lib/kobject.c index 83198cb37d8d..65fa7bf70c57 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -6,7 +6,7 @@ * Copyright (c) 2006-2007 Greg Kroah-Hartman * Copyright (c) 2006-2007 Novell Inc. * - * Please see the file Documentation/kobject.txt for critical information + * Please see the file Documentation/core-api/kobject.rst for critical information * about using the kobject interface. */ @@ -670,7 +670,7 @@ static void kobject_cleanup(struct kobject *kobj) kobject_name(kobj), kobj, __func__, kobj->parent); if (t && !t->release) - pr_debug("kobject: '%s' (%p): does not have a release() function, it is broken and must be fixed. See Documentation/kobject.txt.\n", + pr_debug("kobject: '%s' (%p): does not have a release() function, it is broken and must be fixed. See Documentation/core-api/kobject.rst.\n", kobject_name(kobj), kobj); /* send "remove" if the caller did not do it but sent "add" */ -- cgit v1.2.3 From 4642289b5f6609b1af152a81b603ae8451df2626 Mon Sep 17 00:00:00 2001 From: Mauro Carvalho Chehab Date: Tue, 14 Apr 2020 18:48:59 +0200 Subject: lib: bitmap.c: get rid of some doc warnings There are two ascii art drawings there. Use a block markup tag there in order to get rid of those warnings: ./lib/bitmap.c:189: WARNING: Unexpected indentation. ./lib/bitmap.c:190: WARNING: Block quote ends without a blank line; unexpected unindent. ./lib/bitmap.c:190: WARNING: Unexpected indentation. ./lib/bitmap.c:191: WARNING: Line block ends without a blank line. It should be noticed that there's actually a syntax violation right now, as something like: /** ... @src: will be handled as a definition for @src parameter, and not as part of a diagram. So, we need to add something before it, in order for this to be processed the way it should. Signed-off-by: Mauro Carvalho Chehab Link: https://lore.kernel.org/r/1e2568fdfa838c1a0d8cc2a1d70dd4b6de99bfb1.1586881715.git.mchehab+huawei@kernel.org Signed-off-by: Jonathan Corbet --- lib/bitmap.c | 31 ++++++++++++++++--------------- 1 file changed, 16 insertions(+), 15 deletions(-) (limited to 'lib') diff --git a/lib/bitmap.c b/lib/bitmap.c index 89260aa342d6..21a7640c5eed 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -182,21 +182,22 @@ EXPORT_SYMBOL(__bitmap_shift_left); * * In pictures, example for a big-endian 32-bit architecture: * - * @src: - * 31 63 - * | | - * 10000000 11000001 11110010 00010101 10000000 11000001 01110010 00010101 - * | | | | - * 16 14 0 32 - * - * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is: - * - * 31 63 - * | | - * 10110000 00011000 00110010 00010101 00010000 00011000 00101110 01000010 - * | | | - * 14 (bit 17 0 32 - * from @src) + * The @src bitmap is:: + * + * 31 63 + * | | + * 10000000 11000001 11110010 00010101 10000000 11000001 01110010 00010101 + * | | | | + * 16 14 0 32 + * + * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is:: + * + * 31 63 + * | | + * 10110000 00011000 00110010 00010101 00010000 00011000 00101110 01000010 + * | | | + * 14 (bit 17 0 32 + * from @src) * * Note that @dst and @src might overlap partially or entirely. * -- cgit v1.2.3 From 14bbe3e33710be52f21d61253a94c5f44a696d02 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Wed, 1 Apr 2020 10:33:43 -0700 Subject: docs: Add rbtree documentation to the core-api This file is close enough to being in rst format that I didn't feel the need to alter it in any way. Signed-off-by: Matthew Wilcox (Oracle) Acked-by: Michel Lespinasse Link: https://lore.kernel.org/r/20200401173343.17472-1-willy@infradead.org Signed-off-by: Jonathan Corbet --- Documentation/core-api/index.rst | 1 + Documentation/core-api/rbtree.rst | 429 +++++++++++++++++++++++++++++++++ Documentation/rbtree.txt | 429 --------------------------------- include/linux/rbtree.h | 2 +- include/linux/rbtree_augmented.h | 2 +- lib/Kconfig | 2 +- tools/include/linux/rbtree.h | 2 +- tools/include/linux/rbtree_augmented.h | 2 +- 8 files changed, 435 insertions(+), 434 deletions(-) create mode 100644 Documentation/core-api/rbtree.rst delete mode 100644 Documentation/rbtree.txt (limited to 'lib') diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst index 49e3da910d9e..b29c4a07beda 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -35,6 +35,7 @@ Library functionality that is used throughout the kernel. xarray idr circular-buffers + rbtree generic-radix-tree packing timekeeping diff --git a/Documentation/core-api/rbtree.rst b/Documentation/core-api/rbtree.rst new file mode 100644 index 000000000000..523d54b60087 --- /dev/null +++ b/Documentation/core-api/rbtree.rst @@ -0,0 +1,429 @@ +================================= +Red-black Trees (rbtree) in Linux +================================= + + +:Date: January 18, 2007 +:Author: Rob Landley + +What are red-black trees, and what are they for? +------------------------------------------------ + +Red-black trees are a type of self-balancing binary search tree, used for +storing sortable key/value data pairs. This differs from radix trees (which +are used to efficiently store sparse arrays and thus use long integer indexes +to insert/access/delete nodes) and hash tables (which are not kept sorted to +be easily traversed in order, and must be tuned for a specific size and +hash function where rbtrees scale gracefully storing arbitrary keys). + +Red-black trees are similar to AVL trees, but provide faster real-time bounded +worst case performance for insertion and deletion (at most two rotations and +three rotations, respectively, to balance the tree), with slightly slower +(but still O(log n)) lookup time. + +To quote Linux Weekly News: + + There are a number of red-black trees in use in the kernel. + The deadline and CFQ I/O schedulers employ rbtrees to + track requests; the packet CD/DVD driver does the same. + The high-resolution timer code uses an rbtree to organize outstanding + timer requests. The ext3 filesystem tracks directory entries in a + red-black tree. Virtual memory areas (VMAs) are tracked with red-black + trees, as are epoll file descriptors, cryptographic keys, and network + packets in the "hierarchical token bucket" scheduler. + +This document covers use of the Linux rbtree implementation. For more +information on the nature and implementation of Red Black Trees, see: + + Linux Weekly News article on red-black trees + http://lwn.net/Articles/184495/ + + Wikipedia entry on red-black trees + http://en.wikipedia.org/wiki/Red-black_tree + +Linux implementation of red-black trees +--------------------------------------- + +Linux's rbtree implementation lives in the file "lib/rbtree.c". To use it, +"#include ". + +The Linux rbtree implementation is optimized for speed, and thus has one +less layer of indirection (and better cache locality) than more traditional +tree implementations. Instead of using pointers to separate rb_node and data +structures, each instance of struct rb_node is embedded in the data structure +it organizes. And instead of using a comparison callback function pointer, +users are expected to write their own tree search and insert functions +which call the provided rbtree functions. Locking is also left up to the +user of the rbtree code. + +Creating a new rbtree +--------------------- + +Data nodes in an rbtree tree are structures containing a struct rb_node member:: + + struct mytype { + struct rb_node node; + char *keystring; + }; + +When dealing with a pointer to the embedded struct rb_node, the containing data +structure may be accessed with the standard container_of() macro. In addition, +individual members may be accessed directly via rb_entry(node, type, member). + +At the root of each rbtree is an rb_root structure, which is initialized to be +empty via: + + struct rb_root mytree = RB_ROOT; + +Searching for a value in an rbtree +---------------------------------- + +Writing a search function for your tree is fairly straightforward: start at the +root, compare each value, and follow the left or right branch as necessary. + +Example:: + + struct mytype *my_search(struct rb_root *root, char *string) + { + struct rb_node *node = root->rb_node; + + while (node) { + struct mytype *data = container_of(node, struct mytype, node); + int result; + + result = strcmp(string, data->keystring); + + if (result < 0) + node = node->rb_left; + else if (result > 0) + node = node->rb_right; + else + return data; + } + return NULL; + } + +Inserting data into an rbtree +----------------------------- + +Inserting data in the tree involves first searching for the place to insert the +new node, then inserting the node and rebalancing ("recoloring") the tree. + +The search for insertion differs from the previous search by finding the +location of the pointer on which to graft the new node. The new node also +needs a link to its parent node for rebalancing purposes. + +Example:: + + int my_insert(struct rb_root *root, struct mytype *data) + { + struct rb_node **new = &(root->rb_node), *parent = NULL; + + /* Figure out where to put new node */ + while (*new) { + struct mytype *this = container_of(*new, struct mytype, node); + int result = strcmp(data->keystring, this->keystring); + + parent = *new; + if (result < 0) + new = &((*new)->rb_left); + else if (result > 0) + new = &((*new)->rb_right); + else + return FALSE; + } + + /* Add new node and rebalance tree. */ + rb_link_node(&data->node, parent, new); + rb_insert_color(&data->node, root); + + return TRUE; + } + +Removing or replacing existing data in an rbtree +------------------------------------------------ + +To remove an existing node from a tree, call:: + + void rb_erase(struct rb_node *victim, struct rb_root *tree); + +Example:: + + struct mytype *data = mysearch(&mytree, "walrus"); + + if (data) { + rb_erase(&data->node, &mytree); + myfree(data); + } + +To replace an existing node in a tree with a new one with the same key, call:: + + void rb_replace_node(struct rb_node *old, struct rb_node *new, + struct rb_root *tree); + +Replacing a node this way does not re-sort the tree: If the new node doesn't +have the same key as the old node, the rbtree will probably become corrupted. + +Iterating through the elements stored in an rbtree (in sort order) +------------------------------------------------------------------ + +Four functions are provided for iterating through an rbtree's contents in +sorted order. These work on arbitrary trees, and should not need to be +modified or wrapped (except for locking purposes):: + + struct rb_node *rb_first(struct rb_root *tree); + struct rb_node *rb_last(struct rb_root *tree); + struct rb_node *rb_next(struct rb_node *node); + struct rb_node *rb_prev(struct rb_node *node); + +To start iterating, call rb_first() or rb_last() with a pointer to the root +of the tree, which will return a pointer to the node structure contained in +the first or last element in the tree. To continue, fetch the next or previous +node by calling rb_next() or rb_prev() on the current node. This will return +NULL when there are no more nodes left. + +The iterator functions return a pointer to the embedded struct rb_node, from +which the containing data structure may be accessed with the container_of() +macro, and individual members may be accessed directly via +rb_entry(node, type, member). + +Example:: + + struct rb_node *node; + for (node = rb_first(&mytree); node; node = rb_next(node)) + printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring); + +Cached rbtrees +-------------- + +Computing the leftmost (smallest) node is quite a common task for binary +search trees, such as for traversals or users relying on a the particular +order for their own logic. To this end, users can use 'struct rb_root_cached' +to optimize O(logN) rb_first() calls to a simple pointer fetch avoiding +potentially expensive tree iterations. This is done at negligible runtime +overhead for maintanence; albeit larger memory footprint. + +Similar to the rb_root structure, cached rbtrees are initialized to be +empty via:: + + struct rb_root_cached mytree = RB_ROOT_CACHED; + +Cached rbtree is simply a regular rb_root with an extra pointer to cache the +leftmost node. This allows rb_root_cached to exist wherever rb_root does, +which permits augmented trees to be supported as well as only a few extra +interfaces:: + + struct rb_node *rb_first_cached(struct rb_root_cached *tree); + void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool); + void rb_erase_cached(struct rb_node *node, struct rb_root_cached *); + +Both insert and erase calls have their respective counterpart of augmented +trees:: + + void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *, + bool, struct rb_augment_callbacks *); + void rb_erase_augmented_cached(struct rb_node *, struct rb_root_cached *, + struct rb_augment_callbacks *); + + +Support for Augmented rbtrees +----------------------------- + +Augmented rbtree is an rbtree with "some" additional data stored in +each node, where the additional data for node N must be a function of +the contents of all nodes in the subtree rooted at N. This data can +be used to augment some new functionality to rbtree. Augmented rbtree +is an optional feature built on top of basic rbtree infrastructure. +An rbtree user who wants this feature will have to call the augmentation +functions with the user provided augmentation callback when inserting +and erasing nodes. + +C files implementing augmented rbtree manipulation must include + instead of . Note that +linux/rbtree_augmented.h exposes some rbtree implementations details +you are not expected to rely on; please stick to the documented APIs +there and do not include from header files +either so as to minimize chances of your users accidentally relying on +such implementation details. + +On insertion, the user must update the augmented information on the path +leading to the inserted node, then call rb_link_node() as usual and +rb_augment_inserted() instead of the usual rb_insert_color() call. +If rb_augment_inserted() rebalances the rbtree, it will callback into +a user provided function to update the augmented information on the +affected subtrees. + +When erasing a node, the user must call rb_erase_augmented() instead of +rb_erase(). rb_erase_augmented() calls back into user provided functions +to updated the augmented information on affected subtrees. + +In both cases, the callbacks are provided through struct rb_augment_callbacks. +3 callbacks must be defined: + +- A propagation callback, which updates the augmented value for a given + node and its ancestors, up to a given stop point (or NULL to update + all the way to the root). + +- A copy callback, which copies the augmented value for a given subtree + to a newly assigned subtree root. + +- A tree rotation callback, which copies the augmented value for a given + subtree to a newly assigned subtree root AND recomputes the augmented + information for the former subtree root. + +The compiled code for rb_erase_augmented() may inline the propagation and +copy callbacks, which results in a large function, so each augmented rbtree +user should have a single rb_erase_augmented() call site in order to limit +compiled code size. + + +Sample usage +^^^^^^^^^^^^ + +Interval tree is an example of augmented rb tree. Reference - +"Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. +More details about interval trees: + +Classical rbtree has a single key and it cannot be directly used to store +interval ranges like [lo:hi] and do a quick lookup for any overlap with a new +lo:hi or to find whether there is an exact match for a new lo:hi. + +However, rbtree can be augmented to store such interval ranges in a structured +way making it possible to do efficient lookup and exact match. + +This "extra information" stored in each node is the maximum hi +(max_hi) value among all the nodes that are its descendants. This +information can be maintained at each node just be looking at the node +and its immediate children. And this will be used in O(log n) lookup +for lowest match (lowest start address among all possible matches) +with something like:: + + struct interval_tree_node * + interval_tree_first_match(struct rb_root *root, + unsigned long start, unsigned long last) + { + struct interval_tree_node *node; + + if (!root->rb_node) + return NULL; + node = rb_entry(root->rb_node, struct interval_tree_node, rb); + + while (true) { + if (node->rb.rb_left) { + struct interval_tree_node *left = + rb_entry(node->rb.rb_left, + struct interval_tree_node, rb); + if (left->__subtree_last >= start) { + /* + * Some nodes in left subtree satisfy Cond2. + * Iterate to find the leftmost such node N. + * If it also satisfies Cond1, that's the match + * we are looking for. Otherwise, there is no + * matching interval as nodes to the right of N + * can't satisfy Cond1 either. + */ + node = left; + continue; + } + } + if (node->start <= last) { /* Cond1 */ + if (node->last >= start) /* Cond2 */ + return node; /* node is leftmost match */ + if (node->rb.rb_right) { + node = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb); + if (node->__subtree_last >= start) + continue; + } + } + return NULL; /* No match */ + } + } + +Insertion/removal are defined using the following augmented callbacks:: + + static inline unsigned long + compute_subtree_last(struct interval_tree_node *node) + { + unsigned long max = node->last, subtree_last; + if (node->rb.rb_left) { + subtree_last = rb_entry(node->rb.rb_left, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + if (node->rb.rb_right) { + subtree_last = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + return max; + } + + static void augment_propagate(struct rb_node *rb, struct rb_node *stop) + { + while (rb != stop) { + struct interval_tree_node *node = + rb_entry(rb, struct interval_tree_node, rb); + unsigned long subtree_last = compute_subtree_last(node); + if (node->__subtree_last == subtree_last) + break; + node->__subtree_last = subtree_last; + rb = rb_parent(&node->rb); + } + } + + static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) + { + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; + } + + static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) + { + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; + old->__subtree_last = compute_subtree_last(old); + } + + static const struct rb_augment_callbacks augment_callbacks = { + augment_propagate, augment_copy, augment_rotate + }; + + void interval_tree_insert(struct interval_tree_node *node, + struct rb_root *root) + { + struct rb_node **link = &root->rb_node, *rb_parent = NULL; + unsigned long start = node->start, last = node->last; + struct interval_tree_node *parent; + + while (*link) { + rb_parent = *link; + parent = rb_entry(rb_parent, struct interval_tree_node, rb); + if (parent->__subtree_last < last) + parent->__subtree_last = last; + if (start < parent->start) + link = &parent->rb.rb_left; + else + link = &parent->rb.rb_right; + } + + node->__subtree_last = last; + rb_link_node(&node->rb, rb_parent, link); + rb_insert_augmented(&node->rb, root, &augment_callbacks); + } + + void interval_tree_remove(struct interval_tree_node *node, + struct rb_root *root) + { + rb_erase_augmented(&node->rb, root, &augment_callbacks); + } diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt deleted file mode 100644 index 523d54b60087..000000000000 --- a/Documentation/rbtree.txt +++ /dev/null @@ -1,429 +0,0 @@ -================================= -Red-black Trees (rbtree) in Linux -================================= - - -:Date: January 18, 2007 -:Author: Rob Landley - -What are red-black trees, and what are they for? ------------------------------------------------- - -Red-black trees are a type of self-balancing binary search tree, used for -storing sortable key/value data pairs. This differs from radix trees (which -are used to efficiently store sparse arrays and thus use long integer indexes -to insert/access/delete nodes) and hash tables (which are not kept sorted to -be easily traversed in order, and must be tuned for a specific size and -hash function where rbtrees scale gracefully storing arbitrary keys). - -Red-black trees are similar to AVL trees, but provide faster real-time bounded -worst case performance for insertion and deletion (at most two rotations and -three rotations, respectively, to balance the tree), with slightly slower -(but still O(log n)) lookup time. - -To quote Linux Weekly News: - - There are a number of red-black trees in use in the kernel. - The deadline and CFQ I/O schedulers employ rbtrees to - track requests; the packet CD/DVD driver does the same. - The high-resolution timer code uses an rbtree to organize outstanding - timer requests. The ext3 filesystem tracks directory entries in a - red-black tree. Virtual memory areas (VMAs) are tracked with red-black - trees, as are epoll file descriptors, cryptographic keys, and network - packets in the "hierarchical token bucket" scheduler. - -This document covers use of the Linux rbtree implementation. For more -information on the nature and implementation of Red Black Trees, see: - - Linux Weekly News article on red-black trees - http://lwn.net/Articles/184495/ - - Wikipedia entry on red-black trees - http://en.wikipedia.org/wiki/Red-black_tree - -Linux implementation of red-black trees ---------------------------------------- - -Linux's rbtree implementation lives in the file "lib/rbtree.c". To use it, -"#include ". - -The Linux rbtree implementation is optimized for speed, and thus has one -less layer of indirection (and better cache locality) than more traditional -tree implementations. Instead of using pointers to separate rb_node and data -structures, each instance of struct rb_node is embedded in the data structure -it organizes. And instead of using a comparison callback function pointer, -users are expected to write their own tree search and insert functions -which call the provided rbtree functions. Locking is also left up to the -user of the rbtree code. - -Creating a new rbtree ---------------------- - -Data nodes in an rbtree tree are structures containing a struct rb_node member:: - - struct mytype { - struct rb_node node; - char *keystring; - }; - -When dealing with a pointer to the embedded struct rb_node, the containing data -structure may be accessed with the standard container_of() macro. In addition, -individual members may be accessed directly via rb_entry(node, type, member). - -At the root of each rbtree is an rb_root structure, which is initialized to be -empty via: - - struct rb_root mytree = RB_ROOT; - -Searching for a value in an rbtree ----------------------------------- - -Writing a search function for your tree is fairly straightforward: start at the -root, compare each value, and follow the left or right branch as necessary. - -Example:: - - struct mytype *my_search(struct rb_root *root, char *string) - { - struct rb_node *node = root->rb_node; - - while (node) { - struct mytype *data = container_of(node, struct mytype, node); - int result; - - result = strcmp(string, data->keystring); - - if (result < 0) - node = node->rb_left; - else if (result > 0) - node = node->rb_right; - else - return data; - } - return NULL; - } - -Inserting data into an rbtree ------------------------------ - -Inserting data in the tree involves first searching for the place to insert the -new node, then inserting the node and rebalancing ("recoloring") the tree. - -The search for insertion differs from the previous search by finding the -location of the pointer on which to graft the new node. The new node also -needs a link to its parent node for rebalancing purposes. - -Example:: - - int my_insert(struct rb_root *root, struct mytype *data) - { - struct rb_node **new = &(root->rb_node), *parent = NULL; - - /* Figure out where to put new node */ - while (*new) { - struct mytype *this = container_of(*new, struct mytype, node); - int result = strcmp(data->keystring, this->keystring); - - parent = *new; - if (result < 0) - new = &((*new)->rb_left); - else if (result > 0) - new = &((*new)->rb_right); - else - return FALSE; - } - - /* Add new node and rebalance tree. */ - rb_link_node(&data->node, parent, new); - rb_insert_color(&data->node, root); - - return TRUE; - } - -Removing or replacing existing data in an rbtree ------------------------------------------------- - -To remove an existing node from a tree, call:: - - void rb_erase(struct rb_node *victim, struct rb_root *tree); - -Example:: - - struct mytype *data = mysearch(&mytree, "walrus"); - - if (data) { - rb_erase(&data->node, &mytree); - myfree(data); - } - -To replace an existing node in a tree with a new one with the same key, call:: - - void rb_replace_node(struct rb_node *old, struct rb_node *new, - struct rb_root *tree); - -Replacing a node this way does not re-sort the tree: If the new node doesn't -have the same key as the old node, the rbtree will probably become corrupted. - -Iterating through the elements stored in an rbtree (in sort order) ------------------------------------------------------------------- - -Four functions are provided for iterating through an rbtree's contents in -sorted order. These work on arbitrary trees, and should not need to be -modified or wrapped (except for locking purposes):: - - struct rb_node *rb_first(struct rb_root *tree); - struct rb_node *rb_last(struct rb_root *tree); - struct rb_node *rb_next(struct rb_node *node); - struct rb_node *rb_prev(struct rb_node *node); - -To start iterating, call rb_first() or rb_last() with a pointer to the root -of the tree, which will return a pointer to the node structure contained in -the first or last element in the tree. To continue, fetch the next or previous -node by calling rb_next() or rb_prev() on the current node. This will return -NULL when there are no more nodes left. - -The iterator functions return a pointer to the embedded struct rb_node, from -which the containing data structure may be accessed with the container_of() -macro, and individual members may be accessed directly via -rb_entry(node, type, member). - -Example:: - - struct rb_node *node; - for (node = rb_first(&mytree); node; node = rb_next(node)) - printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring); - -Cached rbtrees --------------- - -Computing the leftmost (smallest) node is quite a common task for binary -search trees, such as for traversals or users relying on a the particular -order for their own logic. To this end, users can use 'struct rb_root_cached' -to optimize O(logN) rb_first() calls to a simple pointer fetch avoiding -potentially expensive tree iterations. This is done at negligible runtime -overhead for maintanence; albeit larger memory footprint. - -Similar to the rb_root structure, cached rbtrees are initialized to be -empty via:: - - struct rb_root_cached mytree = RB_ROOT_CACHED; - -Cached rbtree is simply a regular rb_root with an extra pointer to cache the -leftmost node. This allows rb_root_cached to exist wherever rb_root does, -which permits augmented trees to be supported as well as only a few extra -interfaces:: - - struct rb_node *rb_first_cached(struct rb_root_cached *tree); - void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool); - void rb_erase_cached(struct rb_node *node, struct rb_root_cached *); - -Both insert and erase calls have their respective counterpart of augmented -trees:: - - void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *, - bool, struct rb_augment_callbacks *); - void rb_erase_augmented_cached(struct rb_node *, struct rb_root_cached *, - struct rb_augment_callbacks *); - - -Support for Augmented rbtrees ------------------------------ - -Augmented rbtree is an rbtree with "some" additional data stored in -each node, where the additional data for node N must be a function of -the contents of all nodes in the subtree rooted at N. This data can -be used to augment some new functionality to rbtree. Augmented rbtree -is an optional feature built on top of basic rbtree infrastructure. -An rbtree user who wants this feature will have to call the augmentation -functions with the user provided augmentation callback when inserting -and erasing nodes. - -C files implementing augmented rbtree manipulation must include - instead of . Note that -linux/rbtree_augmented.h exposes some rbtree implementations details -you are not expected to rely on; please stick to the documented APIs -there and do not include from header files -either so as to minimize chances of your users accidentally relying on -such implementation details. - -On insertion, the user must update the augmented information on the path -leading to the inserted node, then call rb_link_node() as usual and -rb_augment_inserted() instead of the usual rb_insert_color() call. -If rb_augment_inserted() rebalances the rbtree, it will callback into -a user provided function to update the augmented information on the -affected subtrees. - -When erasing a node, the user must call rb_erase_augmented() instead of -rb_erase(). rb_erase_augmented() calls back into user provided functions -to updated the augmented information on affected subtrees. - -In both cases, the callbacks are provided through struct rb_augment_callbacks. -3 callbacks must be defined: - -- A propagation callback, which updates the augmented value for a given - node and its ancestors, up to a given stop point (or NULL to update - all the way to the root). - -- A copy callback, which copies the augmented value for a given subtree - to a newly assigned subtree root. - -- A tree rotation callback, which copies the augmented value for a given - subtree to a newly assigned subtree root AND recomputes the augmented - information for the former subtree root. - -The compiled code for rb_erase_augmented() may inline the propagation and -copy callbacks, which results in a large function, so each augmented rbtree -user should have a single rb_erase_augmented() call site in order to limit -compiled code size. - - -Sample usage -^^^^^^^^^^^^ - -Interval tree is an example of augmented rb tree. Reference - -"Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. -More details about interval trees: - -Classical rbtree has a single key and it cannot be directly used to store -interval ranges like [lo:hi] and do a quick lookup for any overlap with a new -lo:hi or to find whether there is an exact match for a new lo:hi. - -However, rbtree can be augmented to store such interval ranges in a structured -way making it possible to do efficient lookup and exact match. - -This "extra information" stored in each node is the maximum hi -(max_hi) value among all the nodes that are its descendants. This -information can be maintained at each node just be looking at the node -and its immediate children. And this will be used in O(log n) lookup -for lowest match (lowest start address among all possible matches) -with something like:: - - struct interval_tree_node * - interval_tree_first_match(struct rb_root *root, - unsigned long start, unsigned long last) - { - struct interval_tree_node *node; - - if (!root->rb_node) - return NULL; - node = rb_entry(root->rb_node, struct interval_tree_node, rb); - - while (true) { - if (node->rb.rb_left) { - struct interval_tree_node *left = - rb_entry(node->rb.rb_left, - struct interval_tree_node, rb); - if (left->__subtree_last >= start) { - /* - * Some nodes in left subtree satisfy Cond2. - * Iterate to find the leftmost such node N. - * If it also satisfies Cond1, that's the match - * we are looking for. Otherwise, there is no - * matching interval as nodes to the right of N - * can't satisfy Cond1 either. - */ - node = left; - continue; - } - } - if (node->start <= last) { /* Cond1 */ - if (node->last >= start) /* Cond2 */ - return node; /* node is leftmost match */ - if (node->rb.rb_right) { - node = rb_entry(node->rb.rb_right, - struct interval_tree_node, rb); - if (node->__subtree_last >= start) - continue; - } - } - return NULL; /* No match */ - } - } - -Insertion/removal are defined using the following augmented callbacks:: - - static inline unsigned long - compute_subtree_last(struct interval_tree_node *node) - { - unsigned long max = node->last, subtree_last; - if (node->rb.rb_left) { - subtree_last = rb_entry(node->rb.rb_left, - struct interval_tree_node, rb)->__subtree_last; - if (max < subtree_last) - max = subtree_last; - } - if (node->rb.rb_right) { - subtree_last = rb_entry(node->rb.rb_right, - struct interval_tree_node, rb)->__subtree_last; - if (max < subtree_last) - max = subtree_last; - } - return max; - } - - static void augment_propagate(struct rb_node *rb, struct rb_node *stop) - { - while (rb != stop) { - struct interval_tree_node *node = - rb_entry(rb, struct interval_tree_node, rb); - unsigned long subtree_last = compute_subtree_last(node); - if (node->__subtree_last == subtree_last) - break; - node->__subtree_last = subtree_last; - rb = rb_parent(&node->rb); - } - } - - static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) - { - struct interval_tree_node *old = - rb_entry(rb_old, struct interval_tree_node, rb); - struct interval_tree_node *new = - rb_entry(rb_new, struct interval_tree_node, rb); - - new->__subtree_last = old->__subtree_last; - } - - static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) - { - struct interval_tree_node *old = - rb_entry(rb_old, struct interval_tree_node, rb); - struct interval_tree_node *new = - rb_entry(rb_new, struct interval_tree_node, rb); - - new->__subtree_last = old->__subtree_last; - old->__subtree_last = compute_subtree_last(old); - } - - static const struct rb_augment_callbacks augment_callbacks = { - augment_propagate, augment_copy, augment_rotate - }; - - void interval_tree_insert(struct interval_tree_node *node, - struct rb_root *root) - { - struct rb_node **link = &root->rb_node, *rb_parent = NULL; - unsigned long start = node->start, last = node->last; - struct interval_tree_node *parent; - - while (*link) { - rb_parent = *link; - parent = rb_entry(rb_parent, struct interval_tree_node, rb); - if (parent->__subtree_last < last) - parent->__subtree_last = last; - if (start < parent->start) - link = &parent->rb.rb_left; - else - link = &parent->rb.rb_right; - } - - node->__subtree_last = last; - rb_link_node(&node->rb, rb_parent, link); - rb_insert_augmented(&node->rb, root, &augment_callbacks); - } - - void interval_tree_remove(struct interval_tree_node *node, - struct rb_root *root) - { - rb_erase_augmented(&node->rb, root, &augment_callbacks); - } diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 1fd61a9af45c..d7db17996322 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -11,7 +11,7 @@ I know it's not the cleaner way, but in C (not in C++) to get performances and genericity... - See Documentation/rbtree.txt for documentation and samples. + See Documentation/core-api/rbtree.rst for documentation and samples. */ #ifndef _LINUX_RBTREE_H diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h index 724b0d036b57..d1c53e9d8c75 100644 --- a/include/linux/rbtree_augmented.h +++ b/include/linux/rbtree_augmented.h @@ -21,7 +21,7 @@ * rb_insert_augmented() and rb_erase_augmented() are intended to be public. * The rest are implementation details you are not expected to depend on. * - * See Documentation/rbtree.txt for documentation and samples. + * See Documentation/core-api/rbtree.rst for documentation and samples. */ struct rb_augment_callbacks { diff --git a/lib/Kconfig b/lib/Kconfig index 5d53f9609c25..8005e36c3459 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -427,7 +427,7 @@ config INTERVAL_TREE See: - Documentation/rbtree.txt + Documentation/core-api/rbtree.rst for more information. diff --git a/tools/include/linux/rbtree.h b/tools/include/linux/rbtree.h index e03b1ea23e0e..30dd21f976c3 100644 --- a/tools/include/linux/rbtree.h +++ b/tools/include/linux/rbtree.h @@ -11,7 +11,7 @@ I know it's not the cleaner way, but in C (not in C++) to get performances and genericity... - See Documentation/rbtree.txt for documentation and samples. + See Documentation/core-api/rbtree.rst for documentation and samples. */ #ifndef __TOOLS_LINUX_PERF_RBTREE_H diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h index 381aa948610d..570bb9794421 100644 --- a/tools/include/linux/rbtree_augmented.h +++ b/tools/include/linux/rbtree_augmented.h @@ -23,7 +23,7 @@ * rb_insert_augmented() and rb_erase_augmented() are intended to be public. * The rest are implementation details you are not expected to depend on. * - * See Documentation/rbtree.txt for documentation and samples. + * See Documentation/core-api/rbtree.rst for documentation and samples. */ struct rb_augment_callbacks { -- cgit v1.2.3 From a74e2a226452ea75d26b1f83860bff91a11da1ac Mon Sep 17 00:00:00 2001 From: Mauro Carvalho Chehab Date: Fri, 1 May 2020 17:37:50 +0200 Subject: docs: debugging-via-ohci1394.txt: add it to the core-api book There is an special chapter inside the core-api book about some debug infrastructure like tracepoints and debug objects. It sounded to me that this is the best place to add a chapter explaining how to use a FireWire controller to do remote kernel debugging, as explained on this document. Signed-off-by: Mauro Carvalho Chehab Link: https://lore.kernel.org/r/9b489d36d08ad89d3ad5aefef1f52a0715b29716.1588345503.git.mchehab+huawei@kernel.org Signed-off-by: Jonathan Corbet --- Documentation/admin-guide/kernel-parameters.txt | 2 +- Documentation/core-api/debugging-via-ohci1394.rst | 185 ++++++++++++++++++++++ Documentation/core-api/index.rst | 1 + Documentation/debugging-via-ohci1394.txt | 185 ---------------------- lib/Kconfig.debug | 2 +- 5 files changed, 188 insertions(+), 187 deletions(-) create mode 100644 Documentation/core-api/debugging-via-ohci1394.rst delete mode 100644 Documentation/debugging-via-ohci1394.txt (limited to 'lib') diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt index f2a93c8679e8..d81d29b5dda7 100644 --- a/Documentation/admin-guide/kernel-parameters.txt +++ b/Documentation/admin-guide/kernel-parameters.txt @@ -3329,7 +3329,7 @@ See Documentation/admin-guide/sysctl/vm.rst for details. ohci1394_dma=early [HW] enable debugging via the ohci1394 driver. - See Documentation/debugging-via-ohci1394.txt for more + See Documentation/core-api/debugging-via-ohci1394.rst for more info. olpc_ec_timeout= [OLPC] ms delay when issuing EC commands diff --git a/Documentation/core-api/debugging-via-ohci1394.rst b/Documentation/core-api/debugging-via-ohci1394.rst new file mode 100644 index 000000000000..981ad4f89fd3 --- /dev/null +++ b/Documentation/core-api/debugging-via-ohci1394.rst @@ -0,0 +1,185 @@ +=========================================================================== +Using physical DMA provided by OHCI-1394 FireWire controllers for debugging +=========================================================================== + +Introduction +------------ + +Basically all FireWire controllers which are in use today are compliant +to the OHCI-1394 specification which defines the controller to be a PCI +bus master which uses DMA to offload data transfers from the CPU and has +a "Physical Response Unit" which executes specific requests by employing +PCI-Bus master DMA after applying filters defined by the OHCI-1394 driver. + +Once properly configured, remote machines can send these requests to +ask the OHCI-1394 controller to perform read and write requests on +physical system memory and, for read requests, send the result of +the physical memory read back to the requester. + +With that, it is possible to debug issues by reading interesting memory +locations such as buffers like the printk buffer or the process table. + +Retrieving a full system memory dump is also possible over the FireWire, +using data transfer rates in the order of 10MB/s or more. + +With most FireWire controllers, memory access is limited to the low 4 GB +of physical address space. This can be a problem on IA64 machines where +memory is located mostly above that limit, but it is rarely a problem on +more common hardware such as x86, x86-64 and PowerPC. + +At least LSI FW643e and FW643e2 controllers are known to support access to +physical addresses above 4 GB, but this feature is currently not enabled by +Linux. + +Together with a early initialization of the OHCI-1394 controller for debugging, +this facility proved most useful for examining long debugs logs in the printk +buffer on to debug early boot problems in areas like ACPI where the system +fails to boot and other means for debugging (serial port) are either not +available (notebooks) or too slow for extensive debug information (like ACPI). + +Drivers +------- + +The firewire-ohci driver in drivers/firewire uses filtered physical +DMA by default, which is more secure but not suitable for remote debugging. +Pass the remote_dma=1 parameter to the driver to get unfiltered physical DMA. + +Because the firewire-ohci driver depends on the PCI enumeration to be +completed, an initialization routine which runs pretty early has been +implemented for x86. This routine runs long before console_init() can be +called, i.e. before the printk buffer appears on the console. + +To activate it, enable CONFIG_PROVIDE_OHCI1394_DMA_INIT (Kernel hacking menu: +Remote debugging over FireWire early on boot) and pass the parameter +"ohci1394_dma=early" to the recompiled kernel on boot. + +Tools +----- + +firescope - Originally developed by Benjamin Herrenschmidt, Andi Kleen ported +it from PowerPC to x86 and x86_64 and added functionality, firescope can now +be used to view the printk buffer of a remote machine, even with live update. + +Bernhard Kaindl enhanced firescope to support accessing 64-bit machines +from 32-bit firescope and vice versa: +- http://v3.sk/~lkundrak/firescope/ + +and he implemented fast system dump (alpha version - read README.txt): +- http://halobates.de/firewire/firedump-0.1.tar.bz2 + +There is also a gdb proxy for firewire which allows to use gdb to access +data which can be referenced from symbols found by gdb in vmlinux: +- http://halobates.de/firewire/fireproxy-0.33.tar.bz2 + +The latest version of this gdb proxy (fireproxy-0.34) can communicate (not +yet stable) with kgdb over an memory-based communication module (kgdbom). + +Getting Started +--------------- + +The OHCI-1394 specification regulates that the OHCI-1394 controller must +disable all physical DMA on each bus reset. + +This means that if you want to debug an issue in a system state where +interrupts are disabled and where no polling of the OHCI-1394 controller +for bus resets takes place, you have to establish any FireWire cable +connections and fully initialize all FireWire hardware __before__ the +system enters such state. + +Step-by-step instructions for using firescope with early OHCI initialization: + +1) Verify that your hardware is supported: + + Load the firewire-ohci module and check your kernel logs. + You should see a line similar to:: + + firewire_ohci 0000:15:00.1: added OHCI v1.0 device as card 2, 4 IR + 4 IT + ... contexts, quirks 0x11 + + when loading the driver. If you have no supported controller, many PCI, + CardBus and even some Express cards which are fully compliant to OHCI-1394 + specification are available. If it requires no driver for Windows operating + systems, it most likely is. Only specialized shops have cards which are not + compliant, they are based on TI PCILynx chips and require drivers for Windows + operating systems. + + The mentioned kernel log message contains the string "physUB" if the + controller implements a writable Physical Upper Bound register. This is + required for physical DMA above 4 GB (but not utilized by Linux yet). + +2) Establish a working FireWire cable connection: + + Any FireWire cable, as long at it provides electrically and mechanically + stable connection and has matching connectors (there are small 4-pin and + large 6-pin FireWire ports) will do. + + If an driver is running on both machines you should see a line like:: + + firewire_core 0000:15:00.1: created device fw1: GUID 00061b0020105917, S400 + + on both machines in the kernel log when the cable is plugged in + and connects the two machines. + +3) Test physical DMA using firescope: + + On the debug host, make sure that /dev/fw* is accessible, + then start firescope:: + + $ firescope + Port 0 (/dev/fw1) opened, 2 nodes detected + + FireScope + --------- + Target : + Gen : 1 + [Ctrl-T] choose target + [Ctrl-H] this menu + [Ctrl-Q] quit + + ------> Press Ctrl-T now, the output should be similar to: + + 2 nodes available, local node is: 0 + 0: ffc0, uuid: 00000000 00000000 [LOCAL] + 1: ffc1, uuid: 00279000 ba4bb801 + + Besides the [LOCAL] node, it must show another node without error message. + +4) Prepare for debugging with early OHCI-1394 initialization: + + 4.1) Kernel compilation and installation on debug target + + Compile the kernel to be debugged with CONFIG_PROVIDE_OHCI1394_DMA_INIT + (Kernel hacking: Provide code for enabling DMA over FireWire early on boot) + enabled and install it on the machine to be debugged (debug target). + + 4.2) Transfer the System.map of the debugged kernel to the debug host + + Copy the System.map of the kernel be debugged to the debug host (the host + which is connected to the debugged machine over the FireWire cable). + +5) Retrieving the printk buffer contents: + + With the FireWire cable connected, the OHCI-1394 driver on the debugging + host loaded, reboot the debugged machine, booting the kernel which has + CONFIG_PROVIDE_OHCI1394_DMA_INIT enabled, with the option ohci1394_dma=early. + + Then, on the debugging host, run firescope, for example by using -A:: + + firescope -A System.map-of-debug-target-kernel + + Note: -A automatically attaches to the first non-local node. It only works + reliably if only connected two machines are connected using FireWire. + + After having attached to the debug target, press Ctrl-D to view the + complete printk buffer or Ctrl-U to enter auto update mode and get an + updated live view of recent kernel messages logged on the debug target. + + Call "firescope -h" to get more information on firescope's options. + +Notes +----- + +Documentation and specifications: http://halobates.de/firewire/ + +FireWire is a trademark of Apple Inc. - for more information please refer to: +https://en.wikipedia.org/wiki/FireWire diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst index c00aef843341..2cfd07a34173 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -98,6 +98,7 @@ Interfaces for kernel debugging debug-objects tracepoint + debugging-via-ohci1394 Everything else =============== diff --git a/Documentation/debugging-via-ohci1394.txt b/Documentation/debugging-via-ohci1394.txt deleted file mode 100644 index 981ad4f89fd3..000000000000 --- a/Documentation/debugging-via-ohci1394.txt +++ /dev/null @@ -1,185 +0,0 @@ -=========================================================================== -Using physical DMA provided by OHCI-1394 FireWire controllers for debugging -=========================================================================== - -Introduction ------------- - -Basically all FireWire controllers which are in use today are compliant -to the OHCI-1394 specification which defines the controller to be a PCI -bus master which uses DMA to offload data transfers from the CPU and has -a "Physical Response Unit" which executes specific requests by employing -PCI-Bus master DMA after applying filters defined by the OHCI-1394 driver. - -Once properly configured, remote machines can send these requests to -ask the OHCI-1394 controller to perform read and write requests on -physical system memory and, for read requests, send the result of -the physical memory read back to the requester. - -With that, it is possible to debug issues by reading interesting memory -locations such as buffers like the printk buffer or the process table. - -Retrieving a full system memory dump is also possible over the FireWire, -using data transfer rates in the order of 10MB/s or more. - -With most FireWire controllers, memory access is limited to the low 4 GB -of physical address space. This can be a problem on IA64 machines where -memory is located mostly above that limit, but it is rarely a problem on -more common hardware such as x86, x86-64 and PowerPC. - -At least LSI FW643e and FW643e2 controllers are known to support access to -physical addresses above 4 GB, but this feature is currently not enabled by -Linux. - -Together with a early initialization of the OHCI-1394 controller for debugging, -this facility proved most useful for examining long debugs logs in the printk -buffer on to debug early boot problems in areas like ACPI where the system -fails to boot and other means for debugging (serial port) are either not -available (notebooks) or too slow for extensive debug information (like ACPI). - -Drivers -------- - -The firewire-ohci driver in drivers/firewire uses filtered physical -DMA by default, which is more secure but not suitable for remote debugging. -Pass the remote_dma=1 parameter to the driver to get unfiltered physical DMA. - -Because the firewire-ohci driver depends on the PCI enumeration to be -completed, an initialization routine which runs pretty early has been -implemented for x86. This routine runs long before console_init() can be -called, i.e. before the printk buffer appears on the console. - -To activate it, enable CONFIG_PROVIDE_OHCI1394_DMA_INIT (Kernel hacking menu: -Remote debugging over FireWire early on boot) and pass the parameter -"ohci1394_dma=early" to the recompiled kernel on boot. - -Tools ------ - -firescope - Originally developed by Benjamin Herrenschmidt, Andi Kleen ported -it from PowerPC to x86 and x86_64 and added functionality, firescope can now -be used to view the printk buffer of a remote machine, even with live update. - -Bernhard Kaindl enhanced firescope to support accessing 64-bit machines -from 32-bit firescope and vice versa: -- http://v3.sk/~lkundrak/firescope/ - -and he implemented fast system dump (alpha version - read README.txt): -- http://halobates.de/firewire/firedump-0.1.tar.bz2 - -There is also a gdb proxy for firewire which allows to use gdb to access -data which can be referenced from symbols found by gdb in vmlinux: -- http://halobates.de/firewire/fireproxy-0.33.tar.bz2 - -The latest version of this gdb proxy (fireproxy-0.34) can communicate (not -yet stable) with kgdb over an memory-based communication module (kgdbom). - -Getting Started ---------------- - -The OHCI-1394 specification regulates that the OHCI-1394 controller must -disable all physical DMA on each bus reset. - -This means that if you want to debug an issue in a system state where -interrupts are disabled and where no polling of the OHCI-1394 controller -for bus resets takes place, you have to establish any FireWire cable -connections and fully initialize all FireWire hardware __before__ the -system enters such state. - -Step-by-step instructions for using firescope with early OHCI initialization: - -1) Verify that your hardware is supported: - - Load the firewire-ohci module and check your kernel logs. - You should see a line similar to:: - - firewire_ohci 0000:15:00.1: added OHCI v1.0 device as card 2, 4 IR + 4 IT - ... contexts, quirks 0x11 - - when loading the driver. If you have no supported controller, many PCI, - CardBus and even some Express cards which are fully compliant to OHCI-1394 - specification are available. If it requires no driver for Windows operating - systems, it most likely is. Only specialized shops have cards which are not - compliant, they are based on TI PCILynx chips and require drivers for Windows - operating systems. - - The mentioned kernel log message contains the string "physUB" if the - controller implements a writable Physical Upper Bound register. This is - required for physical DMA above 4 GB (but not utilized by Linux yet). - -2) Establish a working FireWire cable connection: - - Any FireWire cable, as long at it provides electrically and mechanically - stable connection and has matching connectors (there are small 4-pin and - large 6-pin FireWire ports) will do. - - If an driver is running on both machines you should see a line like:: - - firewire_core 0000:15:00.1: created device fw1: GUID 00061b0020105917, S400 - - on both machines in the kernel log when the cable is plugged in - and connects the two machines. - -3) Test physical DMA using firescope: - - On the debug host, make sure that /dev/fw* is accessible, - then start firescope:: - - $ firescope - Port 0 (/dev/fw1) opened, 2 nodes detected - - FireScope - --------- - Target : - Gen : 1 - [Ctrl-T] choose target - [Ctrl-H] this menu - [Ctrl-Q] quit - - ------> Press Ctrl-T now, the output should be similar to: - - 2 nodes available, local node is: 0 - 0: ffc0, uuid: 00000000 00000000 [LOCAL] - 1: ffc1, uuid: 00279000 ba4bb801 - - Besides the [LOCAL] node, it must show another node without error message. - -4) Prepare for debugging with early OHCI-1394 initialization: - - 4.1) Kernel compilation and installation on debug target - - Compile the kernel to be debugged with CONFIG_PROVIDE_OHCI1394_DMA_INIT - (Kernel hacking: Provide code for enabling DMA over FireWire early on boot) - enabled and install it on the machine to be debugged (debug target). - - 4.2) Transfer the System.map of the debugged kernel to the debug host - - Copy the System.map of the kernel be debugged to the debug host (the host - which is connected to the debugged machine over the FireWire cable). - -5) Retrieving the printk buffer contents: - - With the FireWire cable connected, the OHCI-1394 driver on the debugging - host loaded, reboot the debugged machine, booting the kernel which has - CONFIG_PROVIDE_OHCI1394_DMA_INIT enabled, with the option ohci1394_dma=early. - - Then, on the debugging host, run firescope, for example by using -A:: - - firescope -A System.map-of-debug-target-kernel - - Note: -A automatically attaches to the first non-local node. It only works - reliably if only connected two machines are connected using FireWire. - - After having attached to the debug target, press Ctrl-D to view the - complete printk buffer or Ctrl-U to enter auto update mode and get an - updated live view of recent kernel messages logged on the debug target. - - Call "firescope -h" to get more information on firescope's options. - -Notes ------ - -Documentation and specifications: http://halobates.de/firewire/ - -FireWire is a trademark of Apple Inc. - for more information please refer to: -https://en.wikipedia.org/wiki/FireWire diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 50c1f5f08e6f..298e81357c8a 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1508,7 +1508,7 @@ config PROVIDE_OHCI1394_DMA_INIT This code (~1k) is freed after boot. By then, the firewire stack in charge of the OHCI-1394 controllers should be used instead. - See Documentation/debugging-via-ohci1394.txt for more information. + See Documentation/core-api/debugging-via-ohci1394.rst for more information. source "samples/Kconfig" -- cgit v1.2.3