On Sun Mar 17 18:18:46 2024 +0000, Jinoh Kang wrote:
I don't think this holds if we can guarantee capacity ≥ 3:
You're right, in fact we can see straightforwardly that
\newcommand{\OP}{\mathsf{OldPages}} \newcommand{\Ps}{\mathsf{PageSize}} \newcommand{\Hs}{\mathsf{HeadSize}} \newcommand{\Es}{\mathsf{EltSize}} \\[1ex] \begin{align*} 1&> k\\ &> \frac23\cdot\frac\Ps\Es + \frac13\cdot\frac{\OP\cdot\Ps - \Hs}\Es\\[2ex] &> \frac13\cdot\frac{\OP\cdot\Ps - \Hs}\Es\\ &\geq \frac13\cdot\left(\text{\textsf{old capacity}}\right) \end{align*}doesn't hold for (old capacity) ≥ 3, but that doesn't hold for 3⋅EltSize ≤ 2⋅PageSize either (which is currently the case). I'm not saying this code is incorrect, but that this function in isolation could (and arguably should) guard against otherwise benign future patches, such as element size extension or initial capacity adjustment.
I don't see what you mean by that, where is this guarded exactly?
In https://gitlab.winehq.org/wine/wine/-/blob/552cc456d1889ab3ee0dd5ead6c7520c34d030c0/server/fd.c#L2692 and https://gitlab.winehq.org/wine/wine/-/blob/552cc456d1889ab3ee0dd5ead6c7520c34d030c0/server/mapping.c#L1028, others being not a problem a priori due to working on a new empty temporary file.
@rbernon has pointed out that the capacity is always derived from the mapping size, which means that we can assume that the capacity is the greatest that can fill the given mapping.
Rewriting above in terms of old capacity so that truncated (i.e. does not fill the mapping) capacity is ruled out, the inequality (for non-growth) becomes:
```math k > \tfrac12\cdot\mathsf{OldCapacity} + \mathsf{PageSize}/\mathsf{EltSize} ```
In general, for growth rate "1 + *g*", the equation is:
```math k > g\cdot\mathsf{OldCapacity} + \mathsf{PageSize}/\mathsf{EltSize} ```
In the particular case of "*g* = ½" (in this MR), "capacity ≥ 2" is enough to guarantee that the mapping size increases. However, if it's reduced to a more modest growth rate, the minimum bar for capacity increases.
In short, the following two conditions are required for non-growth (the problem of interest):
1. **The element size is greater than the page size.** This might happen if we end up needing larger chunks of data that contains e.g. key state array.
2. **The old capacity is less than *g*<sup>-1</sup> (the inverse of the growth rate minus 1).** This might happen if we decide that the current growth rate is too fast and slow it down. For example, if "*g* = 1/32", then just "capacity = 31" satisfies the condition.
Although it might sound unlikely, I wouldn't completely rule out either possibility. I'd argue that it's always a good idea to insert explicit assertions[^1] locally rather than relying on the implicit environment (invariant conditions upheld by distant functions), especially since we'll probably end up putting more things into the shared mapping as new performance bottlenecks are discovered.
[^1]: One `assert()` statement in this case