| 1525 | } |
| 1526 | |
| 1527 | struct segment suggest_compaction_segment(uint64_t *sizes, size_t n, |
| 1528 | uint8_t factor) |
| 1529 | { |
| 1530 | struct segment seg = { 0 }; |
| 1531 | uint64_t bytes; |
| 1532 | size_t i; |
| 1533 | |
| 1534 | if (!factor) |
| 1535 | factor = DEFAULT_GEOMETRIC_FACTOR; |
| 1536 | |
| 1537 | /* |
| 1538 | * If there are no tables or only a single one then we don't have to |
| 1539 | * compact anything. The sequence is geometric by definition already. |
| 1540 | */ |
| 1541 | if (n <= 1) |
| 1542 | return seg; |
| 1543 | |
| 1544 | /* |
| 1545 | * Find the ending table of the compaction segment needed to restore the |
| 1546 | * geometric sequence. Note that the segment end is exclusive. |
| 1547 | * |
| 1548 | * To do so, we iterate backwards starting from the most recent table |
| 1549 | * until a valid segment end is found. If the preceding table is smaller |
| 1550 | * than the current table multiplied by the geometric factor (2), the |
| 1551 | * compaction segment end has been identified. |
| 1552 | * |
| 1553 | * Tables after the ending point are not added to the byte count because |
| 1554 | * they are already valid members of the geometric sequence. Due to the |
| 1555 | * properties of a geometric sequence, it is not possible for the sum of |
| 1556 | * these tables to exceed the value of the ending point table. |
| 1557 | * |
| 1558 | * Example table size sequence requiring no compaction: |
| 1559 | * 64, 32, 16, 8, 4, 2, 1 |
| 1560 | * |
| 1561 | * Example table size sequence where compaction segment end is set to |
| 1562 | * the last table. Since the segment end is exclusive, the last table is |
| 1563 | * excluded during subsequent compaction and the table with size 3 is |
| 1564 | * the final table included: |
| 1565 | * 64, 32, 16, 8, 4, 3, 1 |
| 1566 | */ |
| 1567 | for (i = n - 1; i > 0; i--) { |
| 1568 | if (sizes[i - 1] < sizes[i] * factor) { |
| 1569 | seg.end = i + 1; |
| 1570 | bytes = sizes[i]; |
| 1571 | break; |
| 1572 | } |
| 1573 | } |
| 1574 | |
| 1575 | /* |
| 1576 | * Find the starting table of the compaction segment by iterating |
| 1577 | * through the remaining tables and keeping track of the accumulated |
| 1578 | * size of all tables seen from the segment end table. The previous |
| 1579 | * table is compared to the accumulated size because the tables from the |
| 1580 | * segment end are merged backwards recursively. |
| 1581 | * |
| 1582 | * Note that we keep iterating even after we have found the first |
| 1583 | * starting point. This is because there may be tables in the stack |
| 1584 | * preceding that first starting point which violate the geometric |
no outgoing calls