From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/12727 Path: news.gmane.org!.POSTED!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate Date: Tue, 17 Apr 2018 15:01:51 -0400 Message-ID: <20180417190151.GE3094@brightrain.aerifal.cx> References: <20180416175436.2384-1-amonakov@ispras.ru> <20180416175436.2384-2-amonakov@ispras.ru> <20180416223918.GA3094@brightrain.aerifal.cx> <20180417155727.GC3094@brightrain.aerifal.cx> <20180417170624.GD3094@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: blaine.gmane.org 1523991600 23841 195.159.176.226 (17 Apr 2018 19:00:00 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 17 Apr 2018 19:00:00 +0000 (UTC) User-Agent: Mutt/1.5.21 (2010-09-15) To: musl@lists.openwall.com Original-X-From: musl-return-12743-gllmg-musl=m.gmane.org@lists.openwall.com Tue Apr 17 20:59:56 2018 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1f8Vpb-000687-Ge for gllmg-musl@m.gmane.org; Tue, 17 Apr 2018 20:59:55 +0200 Original-Received: (qmail 1376 invoked by uid 550); 17 Apr 2018 19:02:03 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 1355 invoked from network); 17 Apr 2018 19:02:03 -0000 Content-Disposition: inline In-Reply-To: <20180417170624.GD3094@brightrain.aerifal.cx> Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:12727 Archived-At: On Tue, Apr 17, 2018 at 01:06:24PM -0400, Rich Felker wrote: > On Tue, Apr 17, 2018 at 11:57:27AM -0400, Rich Felker wrote: > > > Is there a problem with assuming OVERHEAD+SIZE_ALIGN is signed? > > > > Indeed, I didn't notice but it's actually false: > > > > #define SIZE_ALIGN (4*sizeof(size_t)) > > #define OVERHEAD (2*sizeof(size_t)) > > > > So yes it's a problem. > > > > Note that with things fixed so chunk_size is a multiple of SIZE_ALIGN, > > this issue goes away, because all you need is: > > > > if (chunk_size <= 0) return; > > > > This is because (chunk_size>0 && chunk_size%SIZE_ALIGN==0) implies > > (algebraically) chunk_size>=SIZE_ALIGN. > > > > > > I think the above code may also be wrong. start is aligned mod > > > > SIZE_ALIGN, so start+OVERHEAD is misaligned, and therefore not a valid > > > > argument to MEM_TO_CHUNK. Continuing further along this line of > > > > reasoning, aligning start up mod SIZE_ALIGN like you're doing is not > > > > sufficient. There must also be space for a header below the aligned > > > > point. > > > > > > Yes, that's an oversight, but easily corrected: we need to adjust 'start' > > > so it's congruent to -OVERHEAD (rather than 0) modulo SIZE_ALIGN: > > > > > > void __malloc_donate(char *start, char *end) > > > { > > > ssize_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD); > > > > Upon first reading I thought this was just wrong -- it doesn't reserve > > space and align, it only aligns to OVERHEAD mod SIZE_ALIGN, possibly > > without reserving any space. However, I see the space is later > > reserved via start+OVERHEAD (passed to MEM_TO_CHUNK). > > > > > ssize_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end; > > > ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down); > > > > Because OVERHEAD is unsigned, this transits through unsigned and back > > to signed by assignment, but it should be safe anyway... > > > > > if (chunk_size < OVERHEAD + SIZE_ALIGN) return; > > > start += align_start_up; > > > end -= align_end_down; > > > > > > struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end); > > > c->psize = n->csize = C_INUSE; > > > c->csize = n->psize = C_INUSE | chunk_size; > > > bin_chunk(c); > > > } > > > > > > The above addresses the alignment issue, and I've responded to other > > > concerns. Do you need a new patch with this? > > > > I want something that I'm confident is safe to apply. And I want > > progress made reviewing to be a step towards commit, not something > > that gets thrown out every time there's a new version of the patch > > with a completely different approach. > > > > I'm perfectly ok with committing the slightly-fixed variant of your > > first version I posted, and that's probably my leaning unless there's > > a strong reason to prefer a different approach. If there is, the new > > patch needs to be convincing that it's correct, and should not require > > restarting the review process all over again... > > If you prefer the new approach, is the following version okay? It > avoids mixing signed and unsigned arithmetic (or any expressions where > the the value could exceed the range [0,SIZE_MAX/2-1]). > > void __malloc_donate(char *start, char *end) > { > size_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD); > size_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end; > > if (end - start <= OVERHEAD + align_start_up + align_end_down) > return; > start += align_start_up + OVERHEAD; > end -= align_end_down; > > struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end); > c->psize = n->csize = C_INUSE; > c->csize = n->psize = C_INUSE | (end-start); > bin_chunk(c); > } > > Strictly speaking moving +OVERHEAD into start wasn't needed, but I did > it so the idiomatic end-start could be used for the size below rather > than recomputing it in a potentially inconsistent or un-idiomatic way. > > At this point it's actually very close to the proposed fix-up (with > [...] Testing now, at least one problem still remains: end