公开(公告)号：US09256476B2

公开(公告)日：2016-02-09

申请号：US13316476

申请日：2011-12-10

申请人： Paul E. McKenney

发明人： Paul E. McKenney

IPC分类号： G06F9/46 ,  G06F7/00 ,  G06F9/52

CPC分类号： G06F9/522 ,  G06F2209/521

摘要： A technique for expediting the unloading of an operating system kernel module that executes read-copy update (RCU) callback processing code in a computing system having one or more processors. According to embodiments of the disclosed technique, an RCU callback is enqueued so that it can be processed by the kernel module's callback processing code following completion of a grace period in which each of the one or more processors has passed through a quiescent state. An expediting operation is performed to expedite processing of the RCU callback. The RCU callback is then processed and the kernel module is unloaded.

摘要翻译： 一种用于加速卸载在具有一个或多个处理器的计算系统中执行读取复制更新（RCU）回调处理代码的操作系统内核模块的技术。 根据所公开的技术的实施例，RCU回调被排入队列，使得它可以在其中每个一个或多个处理器都经过静止状态的宽限期完成之后被内核模块的回调处理代码处理。 执行加速操作以加快RCU回调的处理。 然后处理RCU回调，并卸载内核模块。

公开(公告)号：US09250978B2

公开(公告)日：2016-02-02

申请号：US13169570

申请日：2011-06-27

申请人： Paul E. McKenney

发明人： Paul E. McKenney

IPC分类号： G06F9/52 ,  G06F13/00

CPC分类号： G06F9/526

摘要： A technique for implementing user-level read-copy update (RCU) with support for asynchronous grace periods. In an example embodiment, a user-level RCU subsystem is established that executes within threads of a user-level multithreaded application. The multithreaded application may comprise one or more reader threads that read RCU-protected data elements in a shared memory. The multithreaded application may further comprise one or more updater threads that perform updates to the RCU-protected data elements in the shared memory and register callbacks to be executed following a grace period in order to free stale data resulting from the updates. The RCU subsystem may implement two or more helper threads (helpers) that are created or selected as needed to track grace periods and execute the callbacks on behalf of the updaters instead of the updaters performing such work themselves.

公开(公告)号：US09218305B2

公开(公告)日：2015-12-22

申请号：US13307202

申请日：2011-11-30

申请人： Paul E. McKenney

发明人： Paul E. McKenney

IPC分类号： G06F12/00 ,  G06F13/16 ,  G06F9/52

CPC分类号： G06F13/1663 ,  G06F9/52

摘要： Data writers desiring to update data without unduly impacting concurrent readers perform a synchronization operation with respect to plural processors or execution threads. The synchronization operation is parallelized using a hierarchical tree having a root node, one or more levels of internal nodes and as many leaf nodes as there are processors or threads. The tree is traversed from the root node to a lowest level of the internal nodes and the following node processing is performed for each node: (1) check the node's children, (2) if the children are leaf nodes, perform the synchronization operation relative to each leaf node's associated processor or thread, and (3) if the children are internal nodes, fan out and repeat the node processing with each internal node representing a new root node. The foregoing node processing is continued until all processors or threads associated with the leaf nodes have performed the synchronization operation.

摘要翻译： 希望更新数据而不会不适当地影响并发读取器的数据写入者对多个处理器或执行线程执行同步操作。 同步操作使用具有根节点，一个或多个内部节点级别和与处理器或线程一样多的叶节点的分层树并行化。 树从根节点遍历到内部节点的最低层，并为每个节点执行以下节点处理：（1）检查节点的子节点，（2）如果子节点是叶节点，执行同步操作相对 到每个叶节点的相关处理器或线程，以及（3）如果子节点是内部节点，则扇出并重复节点处理，每个内部节点表示新的根节点。 继续前述节点处理，直到与叶节点相关联的所有处理器或线程已经执行了同步操作。

公开(公告)号：US09003420B2

公开(公告)日：2015-04-07

申请号：US13475003

申请日：2012-05-18

申请人： Paul E. McKenney

发明人： Paul E. McKenney

IPC分类号： G06F9/46 ,  G06F9/00 ,  G06F9/48 ,  G06F9/52

CPC分类号： G06F9/4881 ,  G06F9/524

摘要： A technique for resolving deadlocks between an RCU subsystem and an operating system scheduler. An RCU reader manipulates a counter when entering and exiting an RCU read-side critical section. At the entry, the counter is incremented. At the exit, the counter is manipulated differently depending on the counter value. A first counter manipulation path is taken when the counter indicates a task-context RCU reader is exiting an outermost RCU read-side critical section. This path includes condition-based processing that may result in invocation of the operating system scheduler. The first path further includes a deadlock protection operation that manipulates the counter to prevent an intervening RCU reader from taking the same path. The second manipulation path is taken when the counter value indicates a task-context RCU reader is exiting a non-outermost RCU read-side critical section, or an RCU reader is nested within the first path. This path bypasses the condition-based processing.

公开(公告)号：US08788543B2

公开(公告)日：2014-07-22

申请号：US12779726

申请日：2010-05-13

申请人： Paul E. McKenney ,  Joshua A. Triplett

发明人： Paul E. McKenney ,  Joshua A. Triplett

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F12/1018

摘要： A system, method and computer program product for resizing a hash table while supporting hash table scalability and concurrency. The hash table has one or more hash buckets each containing one or more items that are chained together in a linked list. Each item in the hash table is processed to determine if the item requires relocation from a first bucket associated with a first table size to second bucket associated with a second table size. If the item requires relocation, it is linked to the second bucket without moving or copying the item in memory. The item is unlinked from the first bucket after waiting until there is no current hash table reader whose search of the hash table could be affected by the unlinking, again without moving or copying the item in memory.

摘要翻译： 一种用于调整哈希表大小的系统，方法和计算机程序产品，同时支持哈希表的可扩展性和并发性。 哈希表具有一个或多个哈希桶，每个哈希桶包含链接在一起的链接列表中的一个或多个项目。 处理哈希表中的每个项目以确定该项目是否需要从与第一表大小相关联的第一桶重定位到与第二表大小相关联的第二桶。 如果项目需要重新定位，它将链接到第二个桶，而不移动或复制内存中的项目。 在等待之后，该项目与第一个存储桶取消关联，直到没有当前的散列表读取器，其哈希表的搜索可能受到取消链接的影响，而不会移动或复制存储器中的项目。

公开(公告)号：US20140108366A1

公开(公告)日：2014-04-17

申请号：US13774694

申请日：2013-02-22

申请人： Paul E. McKenney

发明人： Paul E. McKenney

IPC分类号： G06F17/30

CPC分类号： G06F17/30286 ,  G06F9/4881 ,  G06F17/30008 ,  G06F17/3023

摘要： A technique for improving the performance of RCU-based searches and updates to a shared data element group where readers must see consistent data with respect to the group as a whole. An updater creates one or more new group data elements and assigns each element a new generation number that is different than a global generation number associated with the data element group, allowing readers to track update versions. The updater links the new data elements into the data element group and then updates the global generation number so that referential integrity is maintained. This is done using a generation number element that is referenced by a header pointer for the data element group, and which in turn references or forms part of one of the data elements. After a grace period has elapsed, the any prior version of the generation number element may be freed.

摘要翻译： 一种用于提高基于RCU的搜索和更新共享数据元素组的性能的技术，读者必须查看与整个组相一致的数据。 更新程序创建一个或多个新的组数据元素，并为每个元素分配与数据元素组相关联的全局代数不同的新生成数，从而允许读者跟踪更新版本。 更新程序将新的数据元素链接到数据元素组中，然后更新全局生成数，以便保持引用完整性。 这是使用由数据元素组的标题指针引用的代数元素完成的，而后者又引用或形成其中一个数据元素的一部分。 经过宽限期后，任何先前版本的代数元素都可以被释放。

公开(公告)号：US08495641B2

公开(公告)日：2013-07-23

申请号：US11771570

申请日：2007-06-29

申请人： Paul E. McKenney

发明人： Paul E. McKenney

IPC分类号： G06F9/46 ,  G06F12/00 ,  G06F13/00 ,  G06F13/28

CPC分类号： G06F9/4831 ,  G06F9/52

摘要： A technique for efficiently boosting the priority of a preemptable data reader while resolving races between the priority boosting and the reader exiting a critical section or terminating in order to eliminate impediments to grace period processing that defers the destruction of one or more shared data elements that may be referenced by the reader until the reader is no longer capable of referencing the one or more data elements. A determination is made that the reader is in a read-side critical section and the reader is designated as a candidate for priority boosting. A verification is made that the reader has not exited its critical section or terminated, and the reader's priority is boosted to expedite its completion of the critical section. The reader's priority is decreased following its completion of the critical section.

摘要翻译： 一种用于有效地提高可抢占数据读取器的优先级的技术，同时解决优先级提升和离开临界区的读者之间的竞争，或者终止，以消除宽限期处理的障碍，从而消除一个或多个共享数据元素的破坏， 由读取器引用，直到读取器不再能够引用一个或多个数据元素。 确定读者处于阅读侧关键部分，读者被指定为优先级提升的候选者。 验证了读者尚未退出其关键部分或终止，读者的优先权得到加强，以加快完成关键部分。 在完成关键部分后，读者的优先级将会下降。

公开(公告)号：US20130151811A1

公开(公告)日：2013-06-13

申请号：US13455220

申请日：2012-04-25

申请人： Paul E. McKenney ,  Joshua A. Triplett

发明人： Paul E. McKenney ,  Joshua A. Triplett

IPC分类号： G06F12/10

CPC分类号： G06F17/30949

摘要： Concurrent resizing and modification of a first RCU-protected hash table includes allocating a second RCU-protected hash table, populating it by linking each hash bucket of the second hash table to all hash buckets of the first hash table containing elements that hash to the second hash table bucket, and publishing the second hash table. If the modifying comprises insertion, a new element is inserted at the head of a corresponding bucket in the second hash table. If the modifying comprises deletion, then within an RCU read-side critical section: (1) all pointers in hash buckets of the first and second hash tables that reference the element being deleted are removed or redirected, and (2) the element is freed following a grace period that protects reader references to the deleted element. The first table is freed from memory after awaiting a grace period that protects reader references to the first hash table.

摘要翻译： 并行调整和修改第一RCU保护的散列表包括分配第二RCU保护的散列表，通过将第二散列表的每个哈希桶链接到第一散列表的所有哈希桶来填充它，其中包含散列到第二个哈希表的元素 哈希表桶，并发布第二个散列表。 如果修改包括插入，则在第二散列表中的相应桶的头部插入新元素。 如果修改包括删除，则在RCU读取侧关键部分内：（1）引用要删除的元素的第一个和第二个哈希表的哈希桶中的所有指针被删除或重定向，并且（2）该元素被释放 遵循宽限期，保护读者对已删除元素的引用。 在等待宽限期之后，第一个表从内存中释放出来，保护读者对第一个哈希表的引用。

公开(公告)号：US20120331238A1

公开(公告)日：2012-12-27

申请号：US13454443

申请日：2012-04-24

申请人： Paul E. McKenney

发明人： Paul E. McKenney

IPC分类号： G06F12/00

CPC分类号： G06F9/526

摘要： A technique for implementing user-level read-copy update (RCU) with support for asynchronous grace periods. In an example embodiment, a user-level RCU subsystem is established that executes within threads of a user-level multithreaded application. The multithreaded application may comprise one or more reader threads that read RCU-protected data elements in a shared memory. The multithreaded application may further comprise one or more updater threads that perform updates to the RCU-protected data elements in the shared memory and register callbacks to be executed following a grace period in order to free stale data resulting from the updates. The RCU subsystem may implement two or more helper threads (helpers) that are created or selected as needed to track grace periods and execute the callbacks on behalf of the updaters instead of the updaters performing such work themselves.

摘要翻译： 一种实现用户级读本更新（RCU）的技术，支持异步宽限期。 在示例实施例中，建立了在用户级多线程应用的线程内执行的用户级RCU子系统。 多线程应用可以包括读取共享存储器中的受RCU保护的数据元素的一个或多个读取器线程。 多线程应用程序还可以包括执行对共享存储器中的RCU保护的数据元素的更新的一个或多个更新器线程，并且在宽限期之后注册回调以便释放由更新引起的不稳定数据。 RCU子系统可以实现根据需要创建或选择的两个或更多个辅助线程（帮助器）来跟踪宽限期并代表更新器执行回调，而不是执行此类工作本身的更新器。

公开(公告)号：US08250047B2

公开(公告)日：2012-08-21

申请号：US11134484

申请日：2005-05-20

申请人： Paul E. McKenney ,  Maged M. Michael

发明人： Paul E. McKenney ,  Maged M. Michael

IPC分类号： G06F7/00 ,  G06F17/00

CPC分类号： G06F9/30087 ,  G06F9/526 ,  G06F2209/523

摘要： Hybrid multi-threaded access to data structures is provided in which hazard pointers are used for reads and locks are used for updates. Where a reader is attempting to read a data structure, the reader maintains a hazard pointer to the data structure before reading it, without globally acquiring a lock on the data structure. Upon the reader being finished reading the data structure, it removes the hazard pointer from the data structure. Where an updater is attempting to update the data structure, the updater globally acquires a lock on the data structure before updating it. Upon the updater being finished updating the data structure, it releases the lock from the data structure. To delete the data structure, first it is determined whether any hazard pointers point to the data structure, and where no hazard pointers do, the data structure is deleted.

摘要翻译： 提供对数据结构的混合多线程访问，其中使用危险指针进行读取，锁用于更新。 读者尝试读取数据结构的地方，读者在读取数据结构之前会保留对数据结构的危险指针，而不会全局获取数据结构上的锁定。 读者读完数据结构后，从数据结构中删除危险指针。 在更新程序尝试更新数据结构的地方，更新程序在更新数据结构之前全局获取数据结构的锁定。 在更新程序完成更新数据结构后，它将从数据结构中释放锁。 要删除数据结构，首先确定任何危险指针是否指向数据结构，如果没有危险指针，则删除数据结构。