| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Fix and reorder some #includes Some of these direct dependencies were previously indirect/transitive dependencies. They previously worked -- and continue to work -- as they only required header inclusions. They should be mentioned in CMakeLists.txt, which we can handle in a separate commit. PiperOrigin-RevId: 977974961 Change-Id: Iac66449258d7c8c74e6813c72943550e83bff099 | 1 个月前 | |
Reorder platform-specific #include directives after the others This keeps includes together when they are cleaned up. PiperOrigin-RevId: 968619710 Change-Id: Idbb71fb83308d8792a75fa0e7e86115859534377 | 1 个月前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Synchronization: Consolidate the logic for whether steady clocks are supported for relative timeouts PiperOrigin-RevId: 523789416 Change-Id: Ide4cfdcae9ea7bffca3355c80ea9c8833a9536e6 | 3 年前 | |
Space out GraphCycles ranks so that InsertEdge can often move just one node In debug builds, absl::Mutex deadlock detection records each lock-order edge with GraphCycles::InsertEdge(held, acquired), under a global lock. GraphCycles keeps node ranks in topological order: rank(x) < rank(y) for each edge x->y. When a new edge breaks this order, InsertEdge uses the Pearce-Kelly algorithm to detect a cycle or repair the ranks. Before this change, ranks were a dense permutation of [0, N), and each new slot got the next rank, above all existing nodes. So when a newly created mutex x is held while an older mutex y is acquired, which is common, the edge x->y often breaks the order. Pearce-Kelly then visits every descendant of y that ranks below x (nearly all of them, since x is new), and sorts and renumbers them, just to put one node in order. With no unused ranks between nodes, even moving one node means renumbering everything in between. This change leaves unused ranks between nodes, so that InsertEdge can often fix the order by moving just x or just y: - Ranks are now int64_t, and new slots get ranks 2^32 above the highest rank. All slots, including free slots, are kept in a doubly linked list sorted by rank. As before, a free slot keeps its rank (and now its place in the list), which is reused with the slot. - If rank(x) > rank(y), InsertEdge(x, y) first tries to move x below y, which requires all in-neighbors of x to rank below y. x moves to the midpoint between y and the slot just below y, or 2^32 below the lowest rank if x has no in-neighbors. If x cannot move, InsertEdge tries the symmetric move of y above x, which requires all out-neighbors of y to rank above x. If neither move works, Pearce-Kelly runs as before. - Ranks stay unique by construction: each new rank is strictly between the ranks of two adjacent slots in the list, or beyond the lowest or highest rank, so no other slot can have it. As before, the Pearce-Kelly reorder reassigns the ranks of the reordered nodes among them. It now also gives each one the list place that goes with its new rank. - A move never hides a cycle: the condition for moving x also proves that y cannot reach x, since every node reachable from y ranks at or above y, but every in-neighbor of x ranks below y. The same holds for moving y, so all cycle detection still happens in the Pearce-Kelly path. Why not simply give new nodes decreasing initial ranks (below all existing nodes)? That makes new -> old edges immediately ordered, but it inverts the order for old -> new edges, such as when a long-lived container mutex locks a newly created child mutex, or when a chain of mutexes is acquired in creation order. Every old -> new edge then triggers a Pearce-Kelly traversal and dense renumbering, making sequential chain construction (BM_StressTest) quadratic: O(N) per edge (114 us/node at N=2048 and 2.9 ms/node at N=32768, vs. under 0.5 us/node). Spacing ranks out and moving either endpoint handles both directions in O(degree) time. Limits and trade-offs: - InsertEdge does not try to move x if x has more than 16 in-neighbors to check, or y if y has more than 16 out-neighbors. If neither can move, it falls back to Pearce-Kelly. This bounds the cost of each attempt. - The 2^32 spacing leaves room for about 32 consecutive moves into the gap between two adjacent new slots. When the two ranks around a gap are less than 2 apart, Respace() first spreads out a run of slots around the gap, keeping their order. Starting with the two slots around the gap, the run doubles in size until its slots can be evenly spaced at least 2^16 apart between the ranks just outside it (-2^62 and 2^62 beyond the ends of the list). - Ranks beyond the lowest and highest ones stay within [-2^62, 2^62], which leaves room for about 2^30 moves (or new slots) at each end. When that runs out, all slots are respaced evenly across [-2^61, 2^61] in O(N) time, which leaves room for 2^29 more at each end. - Slot indices are still int32_t, and the ranks have room for 2^31 slots, so there is no new limit on node count. - Node grows by 16 bytes, for the 64-bit rank and two 32-bit list links (with alignment). It was already over 400 bytes, since it holds a 40-entry stack trace. New tests cover each kind of move, the fallbacks to Pearce-Kelly, and both kinds of respacing. A new test-only method, TestOnlySetRankStride(), lets a test make the ranks beyond the lowest and highest ones run out after a few moves, to exercise the respacing of all slots. PiperOrigin-RevId: 999040867 Change-Id: I3353404e681c094b3cbd4978f384c0415200b2ec | 1 小时前 | |
Space out GraphCycles ranks so that InsertEdge can often move just one node In debug builds, absl::Mutex deadlock detection records each lock-order edge with GraphCycles::InsertEdge(held, acquired), under a global lock. GraphCycles keeps node ranks in topological order: rank(x) < rank(y) for each edge x->y. When a new edge breaks this order, InsertEdge uses the Pearce-Kelly algorithm to detect a cycle or repair the ranks. Before this change, ranks were a dense permutation of [0, N), and each new slot got the next rank, above all existing nodes. So when a newly created mutex x is held while an older mutex y is acquired, which is common, the edge x->y often breaks the order. Pearce-Kelly then visits every descendant of y that ranks below x (nearly all of them, since x is new), and sorts and renumbers them, just to put one node in order. With no unused ranks between nodes, even moving one node means renumbering everything in between. This change leaves unused ranks between nodes, so that InsertEdge can often fix the order by moving just x or just y: - Ranks are now int64_t, and new slots get ranks 2^32 above the highest rank. All slots, including free slots, are kept in a doubly linked list sorted by rank. As before, a free slot keeps its rank (and now its place in the list), which is reused with the slot. - If rank(x) > rank(y), InsertEdge(x, y) first tries to move x below y, which requires all in-neighbors of x to rank below y. x moves to the midpoint between y and the slot just below y, or 2^32 below the lowest rank if x has no in-neighbors. If x cannot move, InsertEdge tries the symmetric move of y above x, which requires all out-neighbors of y to rank above x. If neither move works, Pearce-Kelly runs as before. - Ranks stay unique by construction: each new rank is strictly between the ranks of two adjacent slots in the list, or beyond the lowest or highest rank, so no other slot can have it. As before, the Pearce-Kelly reorder reassigns the ranks of the reordered nodes among them. It now also gives each one the list place that goes with its new rank. - A move never hides a cycle: the condition for moving x also proves that y cannot reach x, since every node reachable from y ranks at or above y, but every in-neighbor of x ranks below y. The same holds for moving y, so all cycle detection still happens in the Pearce-Kelly path. Why not simply give new nodes decreasing initial ranks (below all existing nodes)? That makes new -> old edges immediately ordered, but it inverts the order for old -> new edges, such as when a long-lived container mutex locks a newly created child mutex, or when a chain of mutexes is acquired in creation order. Every old -> new edge then triggers a Pearce-Kelly traversal and dense renumbering, making sequential chain construction (BM_StressTest) quadratic: O(N) per edge (114 us/node at N=2048 and 2.9 ms/node at N=32768, vs. under 0.5 us/node). Spacing ranks out and moving either endpoint handles both directions in O(degree) time. Limits and trade-offs: - InsertEdge does not try to move x if x has more than 16 in-neighbors to check, or y if y has more than 16 out-neighbors. If neither can move, it falls back to Pearce-Kelly. This bounds the cost of each attempt. - The 2^32 spacing leaves room for about 32 consecutive moves into the gap between two adjacent new slots. When the two ranks around a gap are less than 2 apart, Respace() first spreads out a run of slots around the gap, keeping their order. Starting with the two slots around the gap, the run doubles in size until its slots can be evenly spaced at least 2^16 apart between the ranks just outside it (-2^62 and 2^62 beyond the ends of the list). - Ranks beyond the lowest and highest ones stay within [-2^62, 2^62], which leaves room for about 2^30 moves (or new slots) at each end. When that runs out, all slots are respaced evenly across [-2^61, 2^61] in O(N) time, which leaves room for 2^29 more at each end. - Slot indices are still int32_t, and the ranks have room for 2^31 slots, so there is no new limit on node count. - Node grows by 16 bytes, for the 64-bit rank and two 32-bit list links (with alignment). It was already over 400 bytes, since it holds a 40-entry stack trace. New tests cover each kind of move, the fallbacks to Pearce-Kelly, and both kinds of respacing. A new test-only method, TestOnlySetRankStride(), lets a test make the ranks beyond the lowest and highest ones run out after a few moves, to exercise the respacing of all slots. PiperOrigin-RevId: 999040867 Change-Id: I3353404e681c094b3cbd4978f384c0415200b2ec | 1 小时前 | |
Space out GraphCycles ranks so that InsertEdge can often move just one node In debug builds, absl::Mutex deadlock detection records each lock-order edge with GraphCycles::InsertEdge(held, acquired), under a global lock. GraphCycles keeps node ranks in topological order: rank(x) < rank(y) for each edge x->y. When a new edge breaks this order, InsertEdge uses the Pearce-Kelly algorithm to detect a cycle or repair the ranks. Before this change, ranks were a dense permutation of [0, N), and each new slot got the next rank, above all existing nodes. So when a newly created mutex x is held while an older mutex y is acquired, which is common, the edge x->y often breaks the order. Pearce-Kelly then visits every descendant of y that ranks below x (nearly all of them, since x is new), and sorts and renumbers them, just to put one node in order. With no unused ranks between nodes, even moving one node means renumbering everything in between. This change leaves unused ranks between nodes, so that InsertEdge can often fix the order by moving just x or just y: - Ranks are now int64_t, and new slots get ranks 2^32 above the highest rank. All slots, including free slots, are kept in a doubly linked list sorted by rank. As before, a free slot keeps its rank (and now its place in the list), which is reused with the slot. - If rank(x) > rank(y), InsertEdge(x, y) first tries to move x below y, which requires all in-neighbors of x to rank below y. x moves to the midpoint between y and the slot just below y, or 2^32 below the lowest rank if x has no in-neighbors. If x cannot move, InsertEdge tries the symmetric move of y above x, which requires all out-neighbors of y to rank above x. If neither move works, Pearce-Kelly runs as before. - Ranks stay unique by construction: each new rank is strictly between the ranks of two adjacent slots in the list, or beyond the lowest or highest rank, so no other slot can have it. As before, the Pearce-Kelly reorder reassigns the ranks of the reordered nodes among them. It now also gives each one the list place that goes with its new rank. - A move never hides a cycle: the condition for moving x also proves that y cannot reach x, since every node reachable from y ranks at or above y, but every in-neighbor of x ranks below y. The same holds for moving y, so all cycle detection still happens in the Pearce-Kelly path. Why not simply give new nodes decreasing initial ranks (below all existing nodes)? That makes new -> old edges immediately ordered, but it inverts the order for old -> new edges, such as when a long-lived container mutex locks a newly created child mutex, or when a chain of mutexes is acquired in creation order. Every old -> new edge then triggers a Pearce-Kelly traversal and dense renumbering, making sequential chain construction (BM_StressTest) quadratic: O(N) per edge (114 us/node at N=2048 and 2.9 ms/node at N=32768, vs. under 0.5 us/node). Spacing ranks out and moving either endpoint handles both directions in O(degree) time. Limits and trade-offs: - InsertEdge does not try to move x if x has more than 16 in-neighbors to check, or y if y has more than 16 out-neighbors. If neither can move, it falls back to Pearce-Kelly. This bounds the cost of each attempt. - The 2^32 spacing leaves room for about 32 consecutive moves into the gap between two adjacent new slots. When the two ranks around a gap are less than 2 apart, Respace() first spreads out a run of slots around the gap, keeping their order. Starting with the two slots around the gap, the run doubles in size until its slots can be evenly spaced at least 2^16 apart between the ranks just outside it (-2^62 and 2^62 beyond the ends of the list). - Ranks beyond the lowest and highest ones stay within [-2^62, 2^62], which leaves room for about 2^30 moves (or new slots) at each end. When that runs out, all slots are respaced evenly across [-2^61, 2^61] in O(N) time, which leaves room for 2^29 more at each end. - Slot indices are still int32_t, and the ranks have room for 2^31 slots, so there is no new limit on node count. - Node grows by 16 bytes, for the 64-bit rank and two 32-bit list links (with alignment). It was already over 400 bytes, since it holds a 40-entry stack trace. New tests cover each kind of move, the fallbacks to Pearce-Kelly, and both kinds of respacing. A new test-only method, TestOnlySetRankStride(), lets a test make the ranks beyond the lowest and highest ones run out after a few moves, to exercise the respacing of all slots. PiperOrigin-RevId: 999040867 Change-Id: I3353404e681c094b3cbd4978f384c0415200b2ec | 1 小时前 | |
Space out GraphCycles ranks so that InsertEdge can often move just one node In debug builds, absl::Mutex deadlock detection records each lock-order edge with GraphCycles::InsertEdge(held, acquired), under a global lock. GraphCycles keeps node ranks in topological order: rank(x) < rank(y) for each edge x->y. When a new edge breaks this order, InsertEdge uses the Pearce-Kelly algorithm to detect a cycle or repair the ranks. Before this change, ranks were a dense permutation of [0, N), and each new slot got the next rank, above all existing nodes. So when a newly created mutex x is held while an older mutex y is acquired, which is common, the edge x->y often breaks the order. Pearce-Kelly then visits every descendant of y that ranks below x (nearly all of them, since x is new), and sorts and renumbers them, just to put one node in order. With no unused ranks between nodes, even moving one node means renumbering everything in between. This change leaves unused ranks between nodes, so that InsertEdge can often fix the order by moving just x or just y: - Ranks are now int64_t, and new slots get ranks 2^32 above the highest rank. All slots, including free slots, are kept in a doubly linked list sorted by rank. As before, a free slot keeps its rank (and now its place in the list), which is reused with the slot. - If rank(x) > rank(y), InsertEdge(x, y) first tries to move x below y, which requires all in-neighbors of x to rank below y. x moves to the midpoint between y and the slot just below y, or 2^32 below the lowest rank if x has no in-neighbors. If x cannot move, InsertEdge tries the symmetric move of y above x, which requires all out-neighbors of y to rank above x. If neither move works, Pearce-Kelly runs as before. - Ranks stay unique by construction: each new rank is strictly between the ranks of two adjacent slots in the list, or beyond the lowest or highest rank, so no other slot can have it. As before, the Pearce-Kelly reorder reassigns the ranks of the reordered nodes among them. It now also gives each one the list place that goes with its new rank. - A move never hides a cycle: the condition for moving x also proves that y cannot reach x, since every node reachable from y ranks at or above y, but every in-neighbor of x ranks below y. The same holds for moving y, so all cycle detection still happens in the Pearce-Kelly path. Why not simply give new nodes decreasing initial ranks (below all existing nodes)? That makes new -> old edges immediately ordered, but it inverts the order for old -> new edges, such as when a long-lived container mutex locks a newly created child mutex, or when a chain of mutexes is acquired in creation order. Every old -> new edge then triggers a Pearce-Kelly traversal and dense renumbering, making sequential chain construction (BM_StressTest) quadratic: O(N) per edge (114 us/node at N=2048 and 2.9 ms/node at N=32768, vs. under 0.5 us/node). Spacing ranks out and moving either endpoint handles both directions in O(degree) time. Limits and trade-offs: - InsertEdge does not try to move x if x has more than 16 in-neighbors to check, or y if y has more than 16 out-neighbors. If neither can move, it falls back to Pearce-Kelly. This bounds the cost of each attempt. - The 2^32 spacing leaves room for about 32 consecutive moves into the gap between two adjacent new slots. When the two ranks around a gap are less than 2 apart, Respace() first spreads out a run of slots around the gap, keeping their order. Starting with the two slots around the gap, the run doubles in size until its slots can be evenly spaced at least 2^16 apart between the ranks just outside it (-2^62 and 2^62 beyond the ends of the list). - Ranks beyond the lowest and highest ones stay within [-2^62, 2^62], which leaves room for about 2^30 moves (or new slots) at each end. When that runs out, all slots are respaced evenly across [-2^61, 2^61] in O(N) time, which leaves room for 2^29 more at each end. - Slot indices are still int32_t, and the ranks have room for 2^31 slots, so there is no new limit on node count. - Node grows by 16 bytes, for the 64-bit rank and two 32-bit list links (with alignment). It was already over 400 bytes, since it holds a 40-entry stack trace. New tests cover each kind of move, the fallbacks to Pearce-Kelly, and both kinds of respacing. A new test-only method, TestOnlySetRankStride(), lets a test make the ranks beyond the lowest and highest ones run out after a few moves, to exercise the respacing of all slots. PiperOrigin-RevId: 999040867 Change-Id: I3353404e681c094b3cbd4978f384c0415200b2ec | 1 小时前 | |
Reorder platform-specific #include directives after the others This keeps includes together when they are cleaned up. PiperOrigin-RevId: 968619710 Change-Id: Idbb71fb83308d8792a75fa0e7e86115859534377 | 1 个月前 | |
Reorder platform-specific #include directives after the others This keeps includes together when they are cleaned up. PiperOrigin-RevId: 968619710 Change-Id: Idbb71fb83308d8792a75fa0e7e86115859534377 | 1 个月前 | |
Fix failure of kernel_timeout_test when sizeof(time_t) == 4. On 32-bit architectures (such as some android arm architectures), sizeof(time_t) is 4 bytes, which saturates timespec at 2038-01-19T03:14:07Z. Comparing infinite timeouts against `absl::Now() + absl::Hours(100000)` causes test failures once `Now() + 100,000h` extends into 2038 (which is now the case). Replace the dynamic `Now() + 100,000h` comparison with a constant `FarFuture()` time point dependent on `sizeof(time_t)` (Jan 1 2038 on 32-bit time_t, Jan 1 2262 on 64-bit time_t). PiperOrigin-RevId: 970570824 Change-Id: Id0c9da99c8689670a7c9fc62990552d6deb2e96c | 1 个月前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Fix and reorder some #includes Some of these direct dependencies were previously indirect/transitive dependencies. They previously worked -- and continue to work -- as they only required header inclusions. They should be mentioned in CMakeLists.txt, which we can handle in a separate commit. PiperOrigin-RevId: 977974961 Change-Id: Iac66449258d7c8c74e6813c72943550e83bff099 | 1 个月前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Avoid using both Win32Waiter and PthreadWaiter on MinGW, and use StdcppWaiter instead. There are various flavors of MinGW, some of which support pthread, and some of which support Win32. Instead of figuring out which platform is being used, just use the generic implementation. PiperOrigin-RevId: 580565507 Change-Id: Ia85fd7496f1e6ebdeadb95202f0039e844826118 | 2 年前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Synchronization: Support true relative timeouts using the POSIX proposed standard pthread_cond_clockwait() and sem_clockwait(). These are currently implemented in glibc >= 2.30. These methods take a clock and use an absolute time with reference to that clock, so KernelTimeout now can produce these values. PiperOrigin-RevId: 522824226 Change-Id: Ife98713f6f95d800b1f8e52d5364a3dbebc4f8a6 | 3 年前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Add an implementation of Waiter that uses std::mutex/std::condition_variable This implementation may at some point become the default on some platforms. Currently not all platforms have widespread support for both real absolute timeouts or real relative timeouts (here "real" means without converting to the other timeout type which is the only one supported by the underlying APIs). In this case we can defer to their standard library to implement correct support. This is not currently the default on any platform Note: The size of WaiterState had to increase to fit the new implementation PiperOrigin-RevId: 518266646 Change-Id: I7f246646a960d6e1b155f9de0bf2f681c5d3d245 | 3 年前 | |
Fix and reorder some #includes Some of these direct dependencies were previously indirect/transitive dependencies. They previously worked -- and continue to work -- as they only required header inclusions. They should be mentioned in CMakeLists.txt, which we can handle in a separate commit. PiperOrigin-RevId: 977974961 Change-Id: Iac66449258d7c8c74e6813c72943550e83bff099 | 1 个月前 | |
Add StdcppWaiter to the end of the list of waiter implementations Since ABSL_INTERNAL_HAVE_STDCPP_WAITER is defined on all systems it is effectively a fallback. I left the condition there in case we have to disable it on some platform in the future. PiperOrigin-RevId: 555629066 Change-Id: I76ca78c7f36d1d02dc4950a44c66903a2aaf2a52 | 3 年前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Synchronization: Refactor Waiter to allow us to write tests Instead of being only able to test the platform Waiter implementation, this allows us to be able to test all Waiter implementations that build on a specific platform. A unittest is added that tests all implementations that work for the platform, and allows us to check that the expected one is being used by printing the name of the selected implementation. PiperOrigin-RevId: 518072415 Change-Id: Ie9e6fcd9d8283b4038e6f4e68a304d2adcc04b19 | 3 年前 | |
Internal cleanup PiperOrigin-RevId: 965514667 Change-Id: I1901575e58aa9545cd91b518ffde6169af523d0f | 1 个月前 | |
Replace std::TRAIT<...>::value with std::TRAIT_v<...> equivalents PiperOrigin-RevId: 927479222 Change-Id: I70c38e557c8527f72bf86281d88621a5eca26df3 | 4 个月前 | |
Avoid using both Win32Waiter and PthreadWaiter on MinGW, and use StdcppWaiter instead. There are various flavors of MinGW, some of which support pthread, and some of which support Win32. Instead of figuring out which platform is being used, just use the generic implementation. PiperOrigin-RevId: 580565507 Change-Id: Ia85fd7496f1e6ebdeadb95202f0039e844826118 | 2 年前 |
| 文件 | 最后提交记录 | 最后更新时间 |
|---|---|---|
| 1 个月前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 3 年前 | ||
| 1 小时前 | ||
| 1 小时前 | ||
| 1 小时前 | ||
| 1 小时前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 1 个月前 | ||
| 2 年前 | ||
| 1 个月前 | ||
| 3 年前 | ||
| 1 个月前 | ||
| 3 年前 | ||
| 1 个月前 | ||
| 3 年前 | ||
| 1 个月前 | ||
| 3 年前 | ||
| 1 个月前 | ||
| 4 个月前 | ||
| 2 年前 |