From nobody Thu Sep 19 00:53:33 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=quarantine dis=none) header.from=suse.com ARC-Seal: i=1; a=rsa-sha256; t=1721660538; cv=none; d=zohomail.com; s=zohoarc; b=WAinbDE3uXNKH0FnsfqfWRkBSdihemMOj5ALBo9/Q1/wGcNxTsO8i6sZucJo+GqSXh2Qzjhbf3KeDs3i3o4RWblZGGakv7DA6mjLmdsf1Paz5pO1VrQR9BID2Gtfh32T3ETf3zc6wF8cBXUIELkwobeLZKLAgVEjrtxSeXaWQBc= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1721660538; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=Cqa/twmVM9OR6b9NQWSPmCXSs3PkuPb764GnljYHV8Y=; b=RMAg/Y7uiXDdvRmvsrQ86ZlWbSfCOIxyCfglOG+D42q+mZRuSq8mgQFQYUyLpmj2lJOjIS1ojMzwfKbex59voQDPRfYWHGo+3l5mpPZixTIRQsanvYmhRbndpvz/Fpps/FwyvzBelnjSta+4EN18mPgNlzs/yhTcTjvtVjkcEjo= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=quarantine dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1721660538437289.0431876451354; Mon, 22 Jul 2024 08:02:18 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.762126.1172271 (Exim 4.92) (envelope-from ) id 1sVuY9-0001gj-4l; Mon, 22 Jul 2024 15:02:05 +0000 Received: by outflank-mailman (output) from mailman id 762126.1172271; Mon, 22 Jul 2024 15:02:05 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1sVuY9-0001ga-1b; Mon, 22 Jul 2024 15:02:05 +0000 Received: by outflank-mailman (input) for mailman id 762126; Mon, 22 Jul 2024 15:02:03 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1sVuY7-0000sY-GC for xen-devel@lists.xenproject.org; Mon, 22 Jul 2024 15:02:03 +0000 Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 59b144a6-483b-11ef-bbfe-fd08da9f4363; Mon, 22 Jul 2024 17:02:01 +0200 (CEST) Received: from imap1.dmz-prg2.suse.org (unknown [10.150.64.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 8016921B50; Mon, 22 Jul 2024 15:02:01 +0000 (UTC) Received: from imap1.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap1.dmz-prg2.suse.org (Postfix) with ESMTPS id 4DFA5136A9; Mon, 22 Jul 2024 15:02:01 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap1.dmz-prg2.suse.org with ESMTPSA id l4l4EWl0nmajVgAAD6G6ig (envelope-from ); Mon, 22 Jul 2024 15:02:01 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 59b144a6-483b-11ef-bbfe-fd08da9f4363 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=susede1; t=1721660521; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Cqa/twmVM9OR6b9NQWSPmCXSs3PkuPb764GnljYHV8Y=; b=OgKluMJAjn+x1h2p8rX38BpdneRC1u+uocS+PBb45If28Gmu2OgYySS68q9x/Xs8eipk/F RAUunhH3THxVgBjhRzZ+ncLfszj36N0Zq43lzmHZzJMeGyRy/13uIZtaGFm3/sOGebB5+V T+iUSFoPh6ek1YEuCskFxxpVY61Dh9o= Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=susede1; t=1721660521; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Cqa/twmVM9OR6b9NQWSPmCXSs3PkuPb764GnljYHV8Y=; b=OgKluMJAjn+x1h2p8rX38BpdneRC1u+uocS+PBb45If28Gmu2OgYySS68q9x/Xs8eipk/F RAUunhH3THxVgBjhRzZ+ncLfszj36N0Zq43lzmHZzJMeGyRy/13uIZtaGFm3/sOGebB5+V T+iUSFoPh6ek1YEuCskFxxpVY61Dh9o= From: Juergen Gross To: minios-devel@lists.xenproject.org, xen-devel@lists.xenproject.org Cc: samuel.thibault@ens-lyon.org, wl@xen.org, Juergen Gross Subject: [PATCH 3/4] mini-os: mm: reduce buddy allocator list administration data Date: Mon, 22 Jul 2024 17:01:40 +0200 Message-ID: <20240722150141.31391-4-jgross@suse.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240722150141.31391-1-jgross@suse.com> References: <20240722150141.31391-1-jgross@suse.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -2.60 X-Spamd-Result: default: False [-2.60 / 50.00]; BAYES_HAM(-3.00)[100.00%]; MID_CONTAINS_FROM(1.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000]; R_MISSING_CHARSET(0.50)[]; MIME_GOOD(-0.10)[text/plain]; RCVD_VIA_SMTP_AUTH(0.00)[]; ARC_NA(0.00)[]; TO_DN_SOME(0.00)[]; MIME_TRACE(0.00)[0:+]; DKIM_SIGNED(0.00)[suse.com:s=susede1]; FUZZY_BLOCKED(0.00)[rspamd.com]; TO_MATCH_ENVRCPT_ALL(0.00)[]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_FIVE(0.00)[5]; FROM_EQ_ENVFROM(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[suse.com:email]; RCVD_COUNT_TWO(0.00)[2]; RCVD_TLS_ALL(0.00)[] X-Spam-Level: X-Spam-Flag: NO X-ZohoMail-DKIM: pass (identity @suse.com) X-ZM-MESSAGEID: 1721660548578116600 Content-Type: text/plain; charset="utf-8" Today the administration data for the buddy allocator's lists consists of 2 arrays: one pointer array and one list element array for easier handling of the lists' tails. Those arrays can be combined into one by dropping the pointer array and using a different list end indicator. Add enqueue and dequeue helpers for better readability. Change the level member type to unsigned int. Signed-off-by: Juergen Gross Reviewed-by: Samuel Thibault --- mm.c | 73 ++++++++++++++++++++++++++++-------------------------------- 1 file changed, 34 insertions(+), 39 deletions(-) diff --git a/mm.c b/mm.c index 2cc49e94..96686a5c 100644 --- a/mm.c +++ b/mm.c @@ -125,16 +125,30 @@ static void map_free(unsigned long first_page, unsign= ed long nr_pages) typedef struct chunk_head_st chunk_head_t; =20 struct chunk_head_st { - chunk_head_t *next; - chunk_head_t **pprev; - int level; + chunk_head_t *next; + chunk_head_t *prev; + unsigned int level; }; =20 /* Linked lists of free chunks of different powers-of-two in size. */ #define FREELIST_SIZE ((sizeof(void *) << 3) - PAGE_SHIFT) -static chunk_head_t *free_head[FREELIST_SIZE]; -static chunk_head_t free_tail[FREELIST_SIZE]; -#define FREELIST_EMPTY(_l) ((_l)->next =3D=3D NULL) +static chunk_head_t free_list[FREELIST_SIZE]; +#define FREELIST_EMPTY(_l) ((_l)->level =3D=3D FREELIST_SIZE) + +static void enqueue_elem(chunk_head_t *elem, unsigned int level) +{ + elem->level =3D level; + elem->next =3D free_list[level].next; + elem->prev =3D &free_list[level]; + elem->next->prev =3D elem; + free_list[level].next =3D elem; +} + +static void dequeue_elem(chunk_head_t *elem) +{ + elem->prev->next =3D elem->next; + elem->next->prev =3D elem->prev; +} =20 /* * Initialise allocator, placing addresses [@min,@max] in free pool. @@ -151,9 +165,9 @@ static void init_page_allocator(unsigned long min, unsi= gned long max) (u_long)to_virt(min), min, (u_long)to_virt(max), max); for ( i =3D 0; i < FREELIST_SIZE; i++ ) { - free_head[i] =3D &free_tail[i]; - free_tail[i].pprev =3D &free_head[i]; - free_tail[i].next =3D NULL; + free_list[i].next =3D &free_list[i]; + free_list[i].prev =3D &free_list[i]; + free_list[i].level =3D FREELIST_SIZE; } =20 min =3D round_pgup(min); @@ -209,12 +223,7 @@ static void init_page_allocator(unsigned long min, uns= igned long max) ch =3D (chunk_head_t *)r_min; r_min +=3D 1UL << i; range -=3D 1UL << i; - i -=3D PAGE_SHIFT; - ch->level =3D i; - ch->next =3D free_head[i]; - ch->pprev =3D &free_head[i]; - ch->next->pprev =3D &ch->next; - free_head[i] =3D ch; + enqueue_elem(ch, i - PAGE_SHIFT); } } =20 @@ -233,17 +242,16 @@ unsigned long alloc_pages(int order) /* Find smallest order which can satisfy the request. */ for ( i =3D order; i < FREELIST_SIZE; i++ ) { - if ( !FREELIST_EMPTY(free_head[i]) ) + if ( !FREELIST_EMPTY(free_list[i].next) ) break; } =20 - if ( i =3D=3D FREELIST_SIZE ) + if ( i >=3D FREELIST_SIZE ) goto no_memory; =20 /* Unlink a chunk. */ - alloc_ch =3D free_head[i]; - free_head[i] =3D alloc_ch->next; - alloc_ch->next->pprev =3D alloc_ch->pprev; + alloc_ch =3D free_list[i].next; + dequeue_elem(alloc_ch); =20 /* We may have to break the chunk a number of times. */ while ( i !=3D order ) @@ -254,13 +262,7 @@ unsigned long alloc_pages(int order) (1UL << (i + PAGE_SHIFT))); =20 /* Create new header for spare chunk. */ - spare_ch->level =3D i; - spare_ch->next =3D free_head[i]; - spare_ch->pprev =3D &free_head[i]; - - /* Link in the spare chunk. */ - spare_ch->next->pprev =3D &spare_ch->next; - free_head[i] =3D spare_ch; + enqueue_elem(spare_ch, i); } =20 map_alloc(PHYS_PFN(to_phys(alloc_ch)), 1UL << order); @@ -308,18 +310,13 @@ void free_pages(void *pointer, int order) } =20 /* We are committed to merging, unlink the chunk */ - *(to_merge_ch->pprev) =3D to_merge_ch->next; - to_merge_ch->next->pprev =3D to_merge_ch->pprev; + dequeue_elem(to_merge_ch); =20 order++; } =20 /* Link the new chunk */ - freed_ch->level =3D order; - freed_ch->next =3D free_head[order]; - freed_ch->pprev =3D &free_head[order]; - freed_ch->next->pprev =3D &freed_ch->next; - free_head[order] =3D freed_ch; + enqueue_elem(freed_ch, order); =20 } EXPORT_SYMBOL(free_pages); @@ -405,13 +402,11 @@ void sanity_check(void) =20 for ( x =3D 0; x < FREELIST_SIZE; x++ ) { - for ( head =3D free_head[x]; !FREELIST_EMPTY(head); head =3D head-= >next ) + for ( head =3D free_list[x].next; !FREELIST_EMPTY(head); + head =3D head->next ) { ASSERT(!allocated_in_map(virt_to_pfn(head))); - if ( head->next ) - ASSERT(head->next->pprev =3D=3D &head->next); + ASSERT(head->next->prev =3D=3D head); } - if ( free_head[x] ) - ASSERT(free_head[x]->pprev =3D=3D &free_head[x]); } } --=20 2.43.0