lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <i7plirck6zcsk4xguy4yonj2dj7dfdnvvsa2hi6sszfnpgws3o@xpzspa7wrtvq>
Date: Tue, 19 Nov 2024 09:15:36 -0500
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Wei Yang <richard.weiyang@...il.com>
Cc: Sidhartha Kumar <sidhartha.kumar@...cle.com>, linux-kernel@...r.kernel.org,
        maple-tree@...ts.infradead.org, linux-mm@...ck.org,
        akpm@...ux-foundation.org
Subject: Re: [PATCH 3/5] maple_tree: use vacant nodes to reduce worst case
 allocations

* Wei Yang <richard.weiyang@...il.com> [241118 21:31]:
> On Mon, Nov 18, 2024 at 11:36:18AM -0500, Sidhartha Kumar wrote:
> >On 11/15/24 8:41 PM, Wei Yang wrote:
> >> On Fri, Nov 15, 2024 at 03:34:55PM -0500, Sidhartha Kumar wrote:
> >> > On 11/15/24 2:52 AM, Wei Yang wrote:
...

> >> 
> >> Hmm... I come up with a case in which vacant_height may not high enough.
> >> 
> >> Here is the subtree where spanning write locates. The first level is the
> >> parent node of the second level nodes.
> >> 
> >>                  vacant node
> >>                  +--------+-+-+-------+
> >>                  |        |l|r|       |
> >>                  +--------+-+-+-------+
> >> 
> >>                  l                 r
> >>      +------+    +----+-------+    +---------+--+    +------+
> >>      |      |    |    |       |    |         |  |    |      |
> >>      +------+    +----+-------+    +---------+--+    +------+
> >>                       ^                      ^
> >> 		     |                      |
> >> 		   index                   last
> >> 
> >> When mas_wr_walk_descend() to node l, mas_is_span_wr() return true since last
> >> is in the right sibling, node r. Let's say the parent is vacant and l/r is
> >> leaf. So the request number is (1 * 3) + 1.
> >> 
> >> Let's assume:
> >> 
> >>    * vacant node is just sufficient
> >>    * l's left part + r's right part is sufficient but not overflow
> >> 
> >> Then the "new vacant node" would be deficient and needs another round
> >> rebalance.
> >> 
> >> For this case, I am afraid it doesn't allocate enough nodes. Or I
> >> misunderstand this?
> >
> >I think you are correct and we need to use the sufficient height which is
> >introduced in patch 5 in the spanning store case similar to how patch 5 uses
> >it for the rebalance store case.
> >
> >	case wr_rebalance:
> >		if (wr_mas->sufficient_height < wr_mas->vacant_height) {
> >			ret = (height - wr_mas->sufficient_height)*2 +1;
> >			break;
> >		}
> >		ret = delta * 2 + 1;
> >		break;
> >
> 
> I have thought about this.
> 
> But the spanning write case seems to be a little special to
> splitting/rebalance.
> 
> It could be both require one more extra slot and may need to be rebalanced.
> We are not sure the exact behavior on converge node. Only check one aspect
> seems not enough.
> 
> Do you think so ?

I'm pretty sure the calculation will need to be different than the
rebalance case.  He was just saying that it's going to need to be like
rebalance, but not the same code.

Let's see what Sid comes up with.

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ