/* * Copyright (C) 2013-2015 Kay Sievers * Copyright (C) 2013-2015 Greg Kroah-Hartman * Copyright (C) 2013-2015 Daniel Mack * Copyright (C) 2013-2015 David Herrmann * Copyright (C) 2013-2015 Linux Foundation * * kdbus is free software; you can redistribute it and/or modify it under * the terms of the GNU Lesser General Public License as published by the * Free Software Foundation; either version 2.1 of the License, or (at * your option) any later version. */ #include #include #include #include #include #include #include #include #include #include "bus.h" #include "domain.h" #include "endpoint.h" #include "fs.h" #include "handle.h" #include "node.h" #include "util.h" /** * DOC: kdbus nodes * * Nodes unify lifetime management across exposed kdbus objects and provide a * hierarchy. Each kdbus object, that might be exposed to user-space, has a * kdbus_node object embedded and is linked into the hierarchy. Each node can * have any number (0-n) of child nodes linked. Each child retains a reference * to its parent node. For root-nodes, the parent is NULL. * * Each node object goes through a bunch of states during it's lifetime: * * NEW * * LINKED (can be skipped by NEW->FREED transition) * * ACTIVE (can be skipped by LINKED->INACTIVE transition) * * INACTIVE * * DRAINED * * FREED * * Each node is allocated by the caller and initialized via kdbus_node_init(). * This never fails and sets the object into state NEW. From now on, ref-counts * on the node manage its lifetime. During init, the ref-count is set to 1. Once * it drops to 0, the node goes to state FREED and the node->free_cb() callback * is called to deallocate any memory. * * After initializing a node, you usually link it into the hierarchy. You need * to provide a parent node and a name. The node will be linked as child to the * parent and a globally unique ID is assigned to the child. The name of the * child must be unique for all children of this parent. Otherwise, linking the * child will fail with -EEXIST. * Note that the child is not marked active, yet. Admittedly, it prevents any * other node from being linked with the same name (thus, it reserves that * name), but any child-lookup (via name or unique ID) will never return this * child unless it has been marked active. * * Once successfully linked, you can use kdbus_node_activate() to activate a * child. This will mark the child active. This state can be skipped by directly * deactivating the child via kdbus_node_deactivate() (see below). * By activating a child, you enable any lookups on this child to succeed from * now on. Furthermore, any code that got its hands on a reference to the node, * can from now on "acquire" the node. * * Active References (or: 'acquiring' and 'releasing' a node) * Additionally to normal object references, nodes support something we call * "active references". An active reference can be acquired via * kdbus_node_acquire() and released via kdbus_node_release(). A caller * _must_ own a normal object reference whenever calling those functions. * Unlike object references, acquiring an active reference can fail (by * returning 'false' from kdbus_node_acquire()). An active reference can * only be acquired if the node is marked active. If it is not marked * active, yet, or if it was already deactivated, no more active references * can be acquired, ever! * Active references are used to track tasks working on a node. Whenever a * task enters kernel-space to perform an action on a node, it acquires an * active reference, performs the action and releases the reference again. * While holding an active reference, the node is guaranteed to stay active. * If the node is deactivated in parallel, the node is marked as * deactivated, then we wait for all active references to be dropped, before * we finally proceed with any cleanups. That is, if you hold an active * reference to a node, any resources that are bound to the "active" state * are guaranteed to stay accessible until you release your reference. * * Active-references are very similar to rw-locks, where acquiring a node is * equal to try-read-lock and releasing to read-unlock. Deactivating a node * means write-lock and never releasing it again. * Unlike rw-locks, the 'active reference' concept is more versatile and * avoids unusual rw-lock usage (never releasing a write-lock..). * * It is safe to acquire multiple active-references recursively. But you * need to check the return value of kdbus_node_acquire() on _each_ call. It * may stop granting references at _any_ time. * * You're free to perform any operations you want while holding an active * reference, except sleeping for an indefinite period. Sleeping for a fixed * amount of time is fine, but you usually should not wait on wait-queues * without a timeout. * For example, if you wait for I/O to happen, you should gather all data * and schedule the I/O operation, then release your active reference and * wait for it to complete. Then try to acquire a new reference. If it * fails, perform any cleanup (the node is now dead). Otherwise, you can * finish your operation. * * All nodes can be deactivated via kdbus_node_deactivate() at any time. You can * call this multiple times, even in parallel or on nodes that were never * linked, and it will just work. The only restriction is, you must not hold an * active reference when calling kdbus_node_deactivate(). * By deactivating a node, it is immediately marked inactive. Then, we wait for * all active references to be released (called 'draining' the node). This * shouldn't take very long as we don't perform long-lasting operations while * holding an active reference. Note that once the node is marked inactive, no * new active references can be acquired. * Once all active references are dropped, the node is considered 'drained'. Now * kdbus_node_deactivate() is called on each child of the node before we * continue deactivating our node. That is, once all children are entirely * deactivated, we call ->release_cb() of our node. ->release_cb() can release * any resources on that node which are bound to the "active" state of a node. * When done, we unlink the node from its parent rb-tree, mark it as * 'released' and return. * If kdbus_node_deactivate() is called multiple times (even in parallel), all * but one caller will just wait until the node is fully deactivated. That is, * one random caller of kdbus_node_deactivate() is selected to call * ->release_cb() and cleanup the node. Only once all this is done, all other * callers will return from kdbus_node_deactivate(). That is, it doesn't matter * whether you're the selected caller or not, it will only return after * everything is fully done. * * When a node is activated, we acquire a normal object reference to the node. * This reference is dropped after deactivation is fully done (and only iff the * node really was activated). This allows callers to link+activate a child node * and then drop all refs. The node will be deactivated together with the * parent, and then be freed when this reference is dropped. * * Currently, nodes provide a bunch of resources that external code can use * directly. This includes: * * * node->waitq: Each node has its own wait-queue that is used to manage * the 'active' state. When a node is deactivated, we wait on * this queue until all active refs are dropped. Analogously, * when you release an active reference on a deactivated * node, and the active ref-count drops to 0, we wake up a * single thread on this queue. Furthermore, once the * ->release_cb() callback finished, we wake up all waiters. * The node-owner is free to re-use this wait-queue for other * purposes. As node-management uses this queue only during * deactivation, it is usually totally fine to re-use the * queue for other, preferably low-overhead, use-cases. * * * node->type: This field defines the type of the owner of this node. It * must be set during node initialization and must remain * constant. The node management never looks at this value, * but external users might use to gain access to the owner * object of a node. * It is totally up to the owner of the node to define what * their type means. Usually it means you can access the * parent structure via container_of(), as long as you hold an * active reference to the node. * * * node->free_cb: callback after all references are dropped * node->release_cb: callback during node deactivation * These fields must be set by the node owner during * node initialization. They must remain constant. If * NULL, they're skipped. * * * node->mode: filesystem access modes * node->uid: filesystem owner uid * node->gid: filesystem owner gid * These fields must be set by the node owner during node * initialization. They must remain constant and may be * accessed by other callers to properly initialize * filesystem nodes. * * * node->id: This is an unsigned 32bit integer allocated by an IDA. It is * always kept as small as possible during allocation and is * globally unique across all nodes allocated by this module. 0 * is reserved as "not assigned" and is the default. * The ID is assigned during kdbus_node_link() and is kept until * the object is freed. Thus, the ID surpasses the active * lifetime of a node. As long as you hold an object reference * to a node (and the node was linked once), the ID is valid and * unique. * * * node->name: name of this node * node->hash: 31bit hash-value of @name (range [2..INT_MAX-1]) * These values follow the same lifetime rules as node->id. * They're initialized when the node is linked and then remain * constant until the last object reference is dropped. * Unlike the id, the name is only unique across all siblings * and only until the node is deactivated. Currently, the name * is even unique if linked but not activated, yet. This might * change in the future, though. Code should not rely on this. * * * node->lock: lock to protect node->children, node->rb, node->parent * * node->parent: Reference to parent node. This is set during LINK time * and is dropped during destruction. You must not access * it unless you hold an active reference to the node or if * you know the node is dead. * * node->children: rb-tree of all linked children of this node. You must * not access this directly, but use one of the iterator * or lookup helpers. */ /* * Bias values track states of "active references". They're all negative. If a * node is active, its active-ref-counter is >=0 and tracks all active * references. Once a node is deactivaed, we subtract NODE_BIAS. This means, the * counter is now negative but still counts the active references. Once it drops * to exactly NODE_BIAS, we know all active references were dropped. Exactly one * thread will change it to NODE_RELEASE now, perform cleanup and then put it * into NODE_DRAINED. Once drained, all other threads that tried deactivating * the node will now be woken up (thus, they wait until the node is fully done). * The initial state during node-setup is NODE_NEW. If a node is directly * deactivated without having ever been active, it is put into * NODE_RELEASE_DIRECT instead of NODE_BIAS. This tracks this one-bit state * across node-deactivation. The task putting it into NODE_RELEASE now knows * whether the node was active before or not. * * Some archs implement atomic_sub(v) with atomic_add(-v), so reserve INT_MIN * to avoid overflows if multiplied by -1. */ #define KDBUS_NODE_BIAS (INT_MIN + 5) #define KDBUS_NODE_RELEASE_DIRECT (KDBUS_NODE_BIAS - 1) #define KDBUS_NODE_RELEASE (KDBUS_NODE_BIAS - 2) #define KDBUS_NODE_DRAINED (KDBUS_NODE_BIAS - 3) #define KDBUS_NODE_NEW (KDBUS_NODE_BIAS - 4) /* global unique ID mapping for kdbus nodes */ DEFINE_IDA(kdbus_node_ida); /** * kdbus_node_name_hash() - hash a name * @name: The string to hash * * This computes the hash of @name. It is guaranteed to be in the range * [2..INT_MAX-1]. The values 1, 2 and INT_MAX are unused as they are reserved * for the filesystem code. * * Return: hash value of the passed string */ static unsigned int kdbus_node_name_hash(const char *name) { unsigned int hash; /* reserve hash numbers 0, 1 and >=INT_MAX for magic directories */ hash = kdbus_strhash(name) & INT_MAX; if (hash < 2) hash += 2; if (hash >= INT_MAX) hash = INT_MAX - 1; return hash; } /** * kdbus_node_name_compare() - compare a name with a node's name * @hash: hash of the string to compare the node with * @name: name to compare the node with * @node: node to compare the name with * * Return: 0 if @name and @hash exactly match the information in @node, or * an integer less than or greater than zero if @name is found, respectively, * to be less than or be greater than the string stored in @node. */ static int kdbus_node_name_compare(unsigned int hash, const char *name, const struct kdbus_node *node) { if (hash != node->hash) return hash - node->hash; return strcmp(name, node->name); } /** * kdbus_node_init() - initialize a kdbus_node * @node: Pointer to the node to initialize * @type: The type the node will have (KDBUS_NODE_*) * * The caller is responsible of allocating @node and initializating it to zero. * Once this call returns, you must use the node_ref() and node_unref() * functions to manage this node. */ void kdbus_node_init(struct kdbus_node *node, unsigned int type) { atomic_set(&node->refcnt, 1); mutex_init(&node->lock); node->id = 0; node->type = type; RB_CLEAR_NODE(&node->rb); node->children = RB_ROOT; init_waitqueue_head(&node->waitq); atomic_set(&node->active, KDBUS_NODE_NEW); } /** * kdbus_node_link() - link a node into the nodes system * @node: Pointer to the node to initialize * @parent: Pointer to a parent node, may be %NULL * @name: The name of the node (or NULL if root node) * * This links a node into the hierarchy. This must not be called multiple times. * If @parent is NULL, the node becomes a new root node. * * This call will fail if @name is not unique across all its siblings or if no * ID could be allocated. You must not activate a node if linking failed! It is * safe to deactivate it, though. * * Once you linked a node, you must call kdbus_node_deactivate() before you drop * the last reference (even if you never activate the node). * * Return: 0 on success. negative error otherwise. */ int kdbus_node_link(struct kdbus_node *node, struct kdbus_node *parent, const char *name) { int ret; if (WARN_ON(node->type != KDBUS_NODE_DOMAIN && !parent)) return -EINVAL; if (WARN_ON(parent && !name)) return -EINVAL; if (name) { node->name = kstrdup(name, GFP_KERNEL); if (!node->name) return -ENOMEM; node->hash = kdbus_node_name_hash(name); } ret = ida_simple_get(&kdbus_node_ida, 1, 0, GFP_KERNEL); if (ret < 0) return ret; node->id = ret; ret = 0; if (parent) { struct rb_node **n, *prev; if (!kdbus_node_acquire(parent)) return -ESHUTDOWN; mutex_lock(&parent->lock); n = &parent->children.rb_node; prev = NULL; while (*n) { struct kdbus_node *pos; int result; pos = kdbus_node_from_rb(*n); prev = *n; result = kdbus_node_name_compare(node->hash, node->name, pos); if (result == 0) { ret = -EEXIST; goto exit_unlock; } if (result < 0) n = &pos->rb.rb_left; else n = &pos->rb.rb_right; } /* add new node and rebalance the tree */ rb_link_node(&node->rb, prev, n); rb_insert_color(&node->rb, &parent->children); node->parent = kdbus_node_ref(parent); exit_unlock: mutex_unlock(&parent->lock); kdbus_node_release(parent); } return ret; } /** * kdbus_node_ref() - Acquire object reference * @node: node to acquire reference to (or NULL) * * This acquires a new reference to @node. You must already own a reference when * calling this! * If @node is NULL, this is a no-op. * * Return: @node is returned */ struct kdbus_node *kdbus_node_ref(struct kdbus_node *node) { if (node) atomic_inc(&node->refcnt); return node; } /** * kdbus_node_unref() - Drop object reference * @node: node to drop reference to (or NULL) * * This drops an object reference to @node. You must not access the node if you * no longer own a reference. * If the ref-count drops to 0, the object will be destroyed (->free_cb will be * called). * * If you linked or activated the node, you must deactivate the node before you * drop your last reference! If you didn't link or activate the node, you can * drop any reference you want. * * Note that this calls into ->free_cb() and thus _might_ sleep. The ->free_cb() * callbacks must not acquire any outer locks, though. So you can safely drop * references while holding locks. * * If @node is NULL, this is a no-op. * * Return: This always returns NULL */ struct kdbus_node *kdbus_node_unref(struct kdbus_node *node) { if (node && atomic_dec_and_test(&node->refcnt)) { struct kdbus_node safe = *node; WARN_ON(atomic_read(&node->active) != KDBUS_NODE_DRAINED); WARN_ON(!RB_EMPTY_NODE(&node->rb)); if (node->free_cb) node->free_cb(node); if (safe.id > 0) ida_simple_remove(&kdbus_node_ida, safe.id); kfree(safe.name); /* * kdbusfs relies on the parent to be available even after the * node was deactivated and unlinked. Therefore, we pin it * until a node is destroyed. */ kdbus_node_unref(safe.parent); } return NULL; } /** * kdbus_node_is_active() - test whether a node is active * @node: node to test * * This checks whether @node is active. That means, @node was linked and * activated by the node owner and hasn't been deactivated, yet. If, and only * if, a node is active, kdbus_node_acquire() will be able to acquire active * references. * * Note that this function does not give any lifetime guarantees. After this * call returns, the node might be deactivated immediately. Normally, what you * want is to acquire a real active reference via kdbus_node_acquire(). * * Return: true if @node is active, false otherwise */ bool kdbus_node_is_active(struct kdbus_node *node) { return atomic_read(&node->active) >= 0; } /** * kdbus_node_is_deactivated() - test whether a node was already deactivated * @node: node to test * * This checks whether kdbus_node_deactivate() was called on @node. Note that * this might be true even if you never deactivated the node directly, but only * one of its ancestors. * * Note that even if this returns 'false', the node might get deactivated * immediately after the call returns. * * Return: true if @node was already deactivated, false if not */ bool kdbus_node_is_deactivated(struct kdbus_node *node) { int v; v = atomic_read(&node->active); return v != KDBUS_NODE_NEW && v < 0; } /** * kdbus_node_activate() - activate a node * @node: node to activate * * This marks @node as active if, and only if, the node wasn't activated nor * deactivated, yet, and the parent is still active. Any but the first call to * kdbus_node_activate() is a no-op. * If you called kdbus_node_deactivate() before, then even the first call to * kdbus_node_activate() will be a no-op. * * This call doesn't give any lifetime guarantees. The node might get * deactivated immediately after this call returns. Or the parent might already * be deactivated, which will make this call a no-op. * * If this call successfully activated a node, it will take an object reference * to it. This reference is dropped after the node is deactivated. Therefore, * the object owner can safely drop their reference to @node iff they know that * its parent node will get deactivated at some point. Once the parent node is * deactivated, it will deactivate all its child and thus drop this reference * again. * * Return: True if this call successfully activated the node, otherwise false. * Note that this might return false, even if the node is still active * (eg., if you called this a second time). */ bool kdbus_node_activate(struct kdbus_node *node) { bool res = false; mutex_lock(&node->lock); if (atomic_read(&node->active) == KDBUS_NODE_NEW) { atomic_sub(KDBUS_NODE_NEW, &node->active); /* activated nodes have ref +1 */ kdbus_node_ref(node); res = true; } mutex_unlock(&node->lock); return res; } /** * kdbus_node_deactivate() - deactivate a node * @node: The node to deactivate. * * This function recursively deactivates this node and all its children. It * returns only once all children and the node itself were recursively disabled * (even if you call this function multiple times in parallel). * * It is safe to call this function on _any_ node that was initialized _any_ * number of times. * * This call may sleep, as it waits for all active references to be dropped. */ void kdbus_node_deactivate(struct kdbus_node *node) { struct kdbus_node *pos, *child; struct rb_node *rb; int v_pre, v_post; pos = node; /* * To avoid recursion, we perform back-tracking while deactivating * nodes. For each node we enter, we first mark the active-counter as * deactivated by adding BIAS. If the node as children, we set the first * child as current position and start over. If the node has no * children, we drain the node by waiting for all active refs to be * dropped and then releasing the node. * * After the node is released, we set its parent as current position * and start over. If the current position was the initial node, we're * done. * * Note that this function can be called in parallel by multiple * callers. We make sure that each node is only released once, and any * racing caller will wait until the other thread fully released that * node. */ for (;;) { /* * Add BIAS to node->active to mark it as inactive. If it was * never active before, immediately mark it as RELEASE_INACTIVE * so we remember this state. * We cannot remember v_pre as we might iterate into the * children, overwriting v_pre, before we can release our node. */ mutex_lock(&pos->lock); v_pre = atomic_read(&pos->active); if (v_pre >= 0) atomic_add_return(KDBUS_NODE_BIAS, &pos->active); else if (v_pre == KDBUS_NODE_NEW) atomic_set(&pos->active, KDBUS_NODE_RELEASE_DIRECT); mutex_unlock(&pos->lock); /* wait until all active references were dropped */ wait_event(pos->waitq, atomic_read(&pos->active) <= KDBUS_NODE_BIAS); mutex_lock(&pos->lock); /* recurse into first child if any */ rb = rb_first(&pos->children); if (rb) { child = kdbus_node_ref(kdbus_node_from_rb(rb)); mutex_unlock(&pos->lock); pos = child; continue; } /* mark object as RELEASE */ v_post = atomic_read(&pos->active); if (v_post == KDBUS_NODE_BIAS || v_post == KDBUS_NODE_RELEASE_DIRECT) atomic_set(&pos->active, KDBUS_NODE_RELEASE); mutex_unlock(&pos->lock); /* * If this is the thread that marked the object as RELEASE, we * perform the actual release. Otherwise, we wait until the * release is done and the node is marked as DRAINED. */ if (v_post == KDBUS_NODE_BIAS || v_post == KDBUS_NODE_RELEASE_DIRECT) { if (pos->release_cb) pos->release_cb(pos, v_post == KDBUS_NODE_BIAS); if (pos->parent) { mutex_lock(&pos->parent->lock); if (!RB_EMPTY_NODE(&pos->rb)) { rb_erase(&pos->rb, &pos->parent->children); RB_CLEAR_NODE(&pos->rb); } mutex_unlock(&pos->parent->lock); } /* mark as DRAINED */ atomic_set(&pos->active, KDBUS_NODE_DRAINED); wake_up_all(&pos->waitq); /* drop VFS cache */ kdbus_fs_flush(pos); /* * If the node was activated and someone subtracted BIAS * from it to deactivate it, we, and only us, are * responsible to release the extra ref-count that was * taken once in kdbus_node_activate(). * If the node was never activated, no-one ever * subtracted BIAS, but instead skipped that state and * immediately went to NODE_RELEASE_DIRECT. In that case * we must not drop the reference. */ if (v_post == KDBUS_NODE_BIAS) kdbus_node_unref(pos); } else { /* wait until object is DRAINED */ wait_event(pos->waitq, atomic_read(&pos->active) == KDBUS_NODE_DRAINED); } /* * We're done with the current node. Continue on its parent * again, which will try deactivating its next child, or itself * if no child is left. * If we've reached our initial node again, we are done and * can safely return. */ if (pos == node) break; child = pos; pos = pos->parent; kdbus_node_unref(child); } } /** * kdbus_node_acquire() - Acquire an active ref on a node * @node: The node * * This acquires an active-reference to @node. This will only succeed if the * node is active. You must release this active reference via * kdbus_node_release() again. * * See the introduction to "active references" for more details. * * Return: %true if @node was non-NULL and active */ bool kdbus_node_acquire(struct kdbus_node *node) { return node && atomic_inc_unless_negative(&node->active); } /** * kdbus_node_release() - Release an active ref on a node * @node: The node * * This releases an active reference that was previously acquired via * kdbus_node_acquire(). See kdbus_node_acquire() for details. */ void kdbus_node_release(struct kdbus_node *node) { if (node && atomic_dec_return(&node->active) == KDBUS_NODE_BIAS) wake_up(&node->waitq); } /** * kdbus_node_find_child() - Find child by name * @node: parent node to search through * @name: name of child node * * This searches through all children of @node for a child-node with name @name. * If not found, or if the child is deactivated, NULL is returned. Otherwise, * the child is acquired and a new reference is returned. * * If you're done with the child, you need to release it and drop your * reference. * * This function does not acquire the parent node. However, if the parent was * already deactivated, then kdbus_node_deactivate() will, at some point, also * deactivate the child. Therefore, we can rely on the explicit ordering during * deactivation. * * Return: Reference to acquired child node, or NULL if not found / not active. */ struct kdbus_node *kdbus_node_find_child(struct kdbus_node *node, const char *name) { struct kdbus_node *child; struct rb_node *rb; unsigned int hash; int ret; hash = kdbus_node_name_hash(name); mutex_lock(&node->lock); rb = node->children.rb_node; while (rb) { child = kdbus_node_from_rb(rb); ret = kdbus_node_name_compare(hash, name, child); if (ret < 0) rb = rb->rb_left; else if (ret > 0) rb = rb->rb_right; else break; } if (rb && kdbus_node_acquire(child)) kdbus_node_ref(child); else child = NULL; mutex_unlock(&node->lock); return child; } static struct kdbus_node *node_find_closest_unlocked(struct kdbus_node *node, unsigned int hash, const char *name) { struct kdbus_node *n, *pos = NULL; struct rb_node *rb; int res; /* * Find the closest child with ``node->hash >= hash'', or, if @name is * valid, ``node->name >= name'' (where '>=' is the lex. order). */ rb = node->children.rb_node; while (rb) { n = kdbus_node_from_rb(rb); if (name) res = kdbus_node_name_compare(hash, name, n); else res = hash - n->hash; if (res <= 0) { rb = rb->rb_left; pos = n; } else { /* ``hash > n->hash'', ``name > n->name'' */ rb = rb->rb_right; } } return pos; } /** * kdbus_node_find_closest() - Find closest child-match * @node: parent node to search through * @hash: hash value to find closest match for * * Find the closest child of @node with a hash greater than or equal to @hash. * The closest match is the left-most child of @node with this property. Which * means, it is the first child with that hash returned by * kdbus_node_next_child(), if you'd iterate the whole parent node. * * Return: Reference to acquired child, or NULL if none found. */ struct kdbus_node *kdbus_node_find_closest(struct kdbus_node *node, unsigned int hash) { struct kdbus_node *child; struct rb_node *rb; mutex_lock(&node->lock); child = node_find_closest_unlocked(node, hash, NULL); while (child && !kdbus_node_acquire(child)) { rb = rb_next(&child->rb); if (rb) child = kdbus_node_from_rb(rb); else child = NULL; } kdbus_node_ref(child); mutex_unlock(&node->lock); return child; } /** * kdbus_node_next_child() - Acquire next child * @node: parent node * @prev: previous child-node position or NULL * * This function returns a reference to the next active child of @node, after * the passed position @prev. If @prev is NULL, a reference to the first active * child is returned. If no more active children are found, NULL is returned. * * This function acquires the next child it returns. If you're done with the * returned pointer, you need to release _and_ unref it. * * The passed in pointer @prev is not modified by this function, and it does * *not* have to be active. If @prev was acquired via different means, or if it * was unlinked from its parent before you pass it in, then this iterator will * still return the next active child (it will have to search through the * rb-tree based on the node-name, though). * However, @prev must not be linked to a different parent than @node! * * Return: Reference to next acquired child, or NULL if at the end. */ struct kdbus_node *kdbus_node_next_child(struct kdbus_node *node, struct kdbus_node *prev) { struct kdbus_node *pos = NULL; struct rb_node *rb; mutex_lock(&node->lock); if (!prev) { /* * New iteration; find first node in rb-tree and try to acquire * it. If we got it, directly return it as first element. * Otherwise, the loop below will find the next active node. */ rb = rb_first(&node->children); if (!rb) goto exit; pos = kdbus_node_from_rb(rb); if (kdbus_node_acquire(pos)) goto exit; } else if (RB_EMPTY_NODE(&prev->rb)) { /* * The current iterator is no longer linked to the rb-tree. Use * its hash value and name to find the next _higher_ node and * acquire it. If we got it, return it as next element. * Otherwise, the loop below will find the next active node. */ pos = node_find_closest_unlocked(node, prev->hash, prev->name); if (!pos) goto exit; if (kdbus_node_acquire(pos)) goto exit; } else { /* * The current iterator is still linked to the parent. Set it * as current position and use the loop below to find the next * active element. */ pos = prev; } /* @pos was already returned or is inactive; find next active node */ do { rb = rb_next(&pos->rb); if (rb) pos = kdbus_node_from_rb(rb); else pos = NULL; } while (pos && !kdbus_node_acquire(pos)); exit: /* @pos is NULL or acquired. Take ref if non-NULL and return it */ kdbus_node_ref(pos); mutex_unlock(&node->lock); return pos; }