From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: passt.top; dmarc=none (p=none dis=none) header.from=gibson.dropbear.id.au Authentication-Results: passt.top; dkim=pass (2048-bit key; secure) header.d=gibson.dropbear.id.au header.i=@gibson.dropbear.id.au header.a=rsa-sha256 header.s=202602 header.b=Gz490Kkn; dkim-atps=neutral Received: from mail.ozlabs.org (mail.ozlabs.org [IPv6:2404:9400:2221:ea00::3]) by passt.top (Postfix) with ESMTPS id 894025A0265 for ; Tue, 02 Jun 2026 02:57:00 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202602; t=1780361811; bh=JVOsXs8rgK+tkyTgfOknMi8SuTMq5syNVGVb5QPoWYw=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=Gz490KkneIEyBiar+ZJsc/d+gcr3QymzAgwJesSCUOloae1Kg2vWM4iCZkRN+oVFm cbtr2o45CRYyImyVRHG1p9Si9ruyZlnAE8t0D8B6AgoZ5o3CasAMtRpHjQLbxGCzfw Ub57Wf5f+5WAV0FBwYocFqZ/j/uCOYwU+hYji1qynTy211BvL01JRCHjele2Z0+N/D B20H726bMzuAZBbZGJ9D0RA6HNQvmdO1RzrgN4EbxYgbFJoNrbjPiNads6Jlb6aP11 By0m/GqIWkUK9keUuvZZY16KTNch4o4jTTB7HvypCNFL4CKua+twuabZUiq5yLpMjg nXSo42JMSbAfg== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4gTsq74vyXz4wJk; Tue, 02 Jun 2026 10:56:51 +1000 (AEST) Date: Tue, 2 Jun 2026 10:56:45 +1000 From: David Gibson To: Stefano Brivio Subject: Re: [PATCH v2 5/6] dhcp: Add option overload Message-ID: References: <20260526123115.1226166-1-anskuma@redhat.com> <20260526123115.1226166-6-anskuma@redhat.com> <20260528210152.738a54df@elisabeth> <20260529090018.32e6d83a@elisabeth> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="xm6SnLtDVYLipK2b" Content-Disposition: inline In-Reply-To: <20260529090018.32e6d83a@elisabeth> Message-ID-Hash: EJOW4UIMIVTNRRVLEJIZAPFLZC4OZGO2 X-Message-ID-Hash: EJOW4UIMIVTNRRVLEJIZAPFLZC4OZGO2 X-MailFrom: dgibson@gandalf.ozlabs.org X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: Anshu Kumari , passt-dev@passt.top, jmaloy@redhat.com, lvivier@redhat.com X-Mailman-Version: 3.3.8 Precedence: list List-Id: Development discussion and patches for passt Archived-At: Archived-At: List-Archive: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --xm6SnLtDVYLipK2b Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, May 29, 2026 at 09:00:19AM +0200, Stefano Brivio wrote: > On Fri, 29 May 2026 15:49:49 +1000 > David Gibson wrote: >=20 > > On Thu, May 28, 2026 at 09:01:53PM +0200, Stefano Brivio wrote: > > > On Wed, 27 May 2026 14:03:44 +1000 > > > David Gibson wrote: > > > =20 > > > > On Tue, May 26, 2026 at 06:01:12PM +0530, Anshu Kumari wrote: =20 > > > > > A user can enter lots of options in command-line which may not fi= t in > > > > > existing buffer, So when the options field is full, overflow rema= ining > > > > > DHCP options into the file and sname fields per RFC 2132 option 5= 2. > > > > >=20 > > > > > Also, when the file field is not used for overload, copy the boot > > > > > file URL there directly for legacy PXE clients. > > > > >=20 > > > > > Link: https://bugs.passt.top/show_bug.cgi?id=3D192 > > > > > Signed-off-by: Anshu Kumari > > > > > --- > > > > > v2: > > > > > - Added #define DHCP_OVERLOAD_FILE and #define DHCP_OVERLOAD_SN= AME constants > > > > > - Added comment documenting space reservation: /* Reserve 3 byt= es for option 52 */ > > > > > - Fixed DNS search length: sizeof(m->o) only, not combined with= file+sname > > > > > - Removed dhcp_boot references =E2=80=94 reply.file copy now re= ads from opts[67] > > > > > - Used DHCP_OVERLOAD_FILE constant in reply.file guard > > > > > --- > > > > > dhcp.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++-= ------ > > > > > 1 file changed, 75 insertions(+), 9 deletions(-) > > > > >=20 > > > > > diff --git a/dhcp.c b/dhcp.c > > > > > index e126063..a49a05a 100644 > > > > > --- a/dhcp.c > > > > > +++ b/dhcp.c > > > > > @@ -306,14 +306,59 @@ static bool fill_one(uint8_t *buf, size_t s= ize, int o, int *offset) > > > > > return false; > > > > > } > > > > > =20 > > > > > +#define DHCP_OVERLOAD_FILE 1 > > > > > +#define DHCP_OVERLOAD_SNAME 2 =20 > > > >=20 > > > > IIUC, these values are from the RFC - might be worth referencing the > > > > relevant section in a comment to make it clear they can't be changed > > > > arbitrarily. > > > > =20 > > > > > + > > > > > +/** > > > > > + * fill_overflow() - Fill remaining options into file and sname = fields > > > > > + * @m: Message whose file/sname fields may be used for overflow > > > > > + * > > > > > + * Return: option 52 overload value: 0 if no overflow, > > > > > + * DHCP_OVERLOAD_FILE for file, DHCP_OVERLOAD_SNAME for = sname, > > > > > + * or both OR'd together > > > > > + */ > > > > > +static int fill_overflow(struct msg *m) > > > > > +{ > > > > > + int file_off =3D 0, sname_off =3D 0, overload =3D 0; > > > > > + int o; > > > > > + > > > > > + for (o =3D 0; o < 255; o++) { =20 > > > >=20 > > > > You could use ARRAY_size(opts) instead of raw 255, yes? > > > > =20 > > > > > + if (opts[o].slen =3D=3D -1 || opts[o].sent) > > > > > + continue; > > > > > + fill_one(m->file, sizeof(m->file) - 1, o, &file_off); > > > > > + } > > > > > + > > > > > + for (o =3D 0; o < 255; o++) { > > > > > + if (opts[o].slen =3D=3D -1 || opts[o].sent) > > > > > + continue; > > > > > + if (fill_one(m->sname, sizeof(m->sname) - 1, o, &sname_off)) > > > > > + debug("DHCP: skipping option %i (overload full)", o); > > > > > + } > > > > > + > > > > > + if (file_off) { > > > > > + m->file[file_off] =3D 255; > > > > > + overload |=3D DHCP_OVERLOAD_FILE; > > > > > + } > > > > > + > > > > > + if (sname_off) { > > > > > + m->sname[sname_off] =3D 255; > > > > > + overload |=3D DHCP_OVERLOAD_SNAME; > > > > > + } > > > > > + > > > > > + return overload; > > > > > +} > > > > > + > > > > > /** > > > > > - * fill() - Fill options in message > > > > > + * fill() - Fill options in message, with overload into file/sna= me if needed > > > > > * @m: Message to fill > > > > > + * @overload: Set to option 52 value (0 if none, 1/2/3 per RFC 2= 132) > > > > > * > > > > > * Return: current size of options field > > > > > */ > > > > > -static int fill(struct msg *m) > > > > > +static int fill(struct msg *m, int *overload) > > > > > { > > > > > + /* Reserve 3 bytes for option 52 (overload) if needed */ > > > > > + size_t size =3D OPT_MAX - 3; > > > > > int i, o, offset =3D 0; > > > > > =20 > > > > > for (o =3D 0; o < 255; o++) > > > > > @@ -324,20 +369,25 @@ static int fill(struct msg *m) > > > > > * Put it there explicitly, unless requested via option 55. > > > > > */ > > > > > if (opts[55].clen > 0 && !memchr(opts[55].c, 53, opts[55].clen)) > > > > > - if (fill_one(m->o, OPT_MAX, 53, &offset)) > > > > > - debug("DHCP: skipping option 53"); > > > > > + fill_one(m->o, size, 53, &offset); > > > > > =20 > > > > > for (i =3D 0; i < opts[55].clen; i++) { > > > > > o =3D opts[55].c[i]; > > > > > if (opts[o].slen !=3D -1) > > > > > - if (fill_one(m->o, OPT_MAX, o, &offset)) > > > > > - debug("DHCP: skipping option %i", o); > > > > > + fill_one(m->o, size, o, &offset); > > > > > } > > > > > =20 > > > > > for (o =3D 0; o < 255; o++) { > > > > > if (opts[o].slen !=3D -1 && !opts[o].sent) > > > > > - if (fill_one(m->o, OPT_MAX, o, &offset)) > > > > > - debug("DHCP: skipping option %i", o); > > > > > + fill_one(m->o, size, o, &offset); > > > > > + } > > > > > + > > > > > + *overload =3D fill_overflow(m); > > > > > + > > > > > + if (*overload) { > > > > > + m->o[offset++] =3D 52; > > > > > + m->o[offset++] =3D 1; > > > > > + m->o[offset++] =3D *overload; > > > > > } > > > > > =20 > > > > > m->o[offset++] =3D 255; > > > > > @@ -462,6 +512,7 @@ int dhcp(const struct ctx *c, struct iov_tail= *data) > > > > > struct msg const *m; > > > > > struct msg reply; > > > > > unsigned int i; > > > > > + int overload; > > > > > =20 > > > > > eh =3D IOV_REMOVE_HEADER(data, eh_storage); > > > > > iph =3D IOV_PEEK_HEADER(data, iph_storage); > > > > > @@ -613,7 +664,22 @@ int dhcp(const struct ctx *c, struct iov_tai= l *data) > > > > > if (!c->no_dhcp_dns_search) > > > > > opt_set_dns_search(c, sizeof(m->o)); > > > > > =20 > > > > > - dlen =3D offsetof(struct msg, o) + fill(&reply); > > > > > + for (i =3D 0; i < (unsigned int)c->custom_opts_count; i++) { > > > > > + uint8_t code =3D c->custom_opts[i].code; > > > > > + > > > > > + opts[code].slen =3D c->custom_opts[i].len; > > > > > + memcpy(opts[code].s, c->custom_opts[i].val, > > > > > + c->custom_opts[i].len); > > > > > + } > > > > > + > > > > > + dlen =3D offsetof(struct msg, o) + fill(&reply, &overload); > > > > > + > > > > > + /* Copy boot file name into the file field for legacy PXE clien= ts, > > > > > + * unless the file field is already used for option overload. = =20 > > > >=20 > > > > Given we do this, would it make more sense to use the slen field in > > > > preference to the file field for overloads? The logic above appears > > > > to do it the other way around, =20 > > >=20 > > > Assuming s/slen/sname/: I didn't really think this through, but there > > > might be a more fundamental advantage in doing this, rather than just > > > the boot file consideration: each single option we add needs to fit > > > entirely in one of the two areas. > > >=20 > > > If we try sname (smaller) first, we *should* have strictly better > > > chances than the other way around. > > >=20 > > > Example: we need to fit (hypothetical) options 20 (20 bytes), option = 30 > > > (30 bytes) and option 120 (120 bytes). If we try 'file' first: > > >=20 > > > - option 20 fits, option 30 fits, nothing else, move to 'sname' > > > - nothing else fits: two options encoded > > >=20 > > > If we try 'sname' first: > > >=20 > > > - option 20 fits, option 30 fits, nothing else, move to 'file' > > > - option 120 fits: three options encoded > > >=20 > > > There must be some relatively simple proof or theorem for this but > > > right now I can't think of any name / reference. =20 > >=20 > > Alas, it's not strictly better. If we were packing the options in > > reverse order (120 byte, then 30 byte, then 20 byte), we get 3 encoded > > if we use file first, 1 encoded if we use sname first. >=20 > Hmm, no, why? Note that Anshu's fill_overflow() loops on all > (remaining) options for both fields, so in that case you would have: Ah, sorry, I missed that, yes, I was thinking it did a single pass through the options. > - sname first: fail to insert 120-byte option in sname, insert 30-byte > option in sname, insert 20-byte option in sname, move to file, insert > 120-byte option in file >=20 > - file first: insert 120-byte option in file, fail to insert 30-byte > option in file, fail to insert 20-byte option in file, move to sname, > insert 30-byte option in sname, insert 20-byte option in sname >=20 > > To do strictly better we'd need to consider separately for each option > > which field we pack it into. That's probably more trouble than it's > > worth. >=20 > It's already done in some sense. Right, I missed that. > My hypothesis is that, by trying the > smallest bin first, the greedy algorithm should already be optimal. I'm > not quite sure but it intuitively makes sense for me. As noted below, I'm pretty sure it's not (strictly) optimal - I suspect that's an NP-hard problem. Good enough in practice, definitely. >=20 > > Even that approach isn't theoretically optimal. This is (almost[1]) > > the multiple subset sum problem for m=3D2 [0]. >=20 > Right! Thanks, that's the one I meant. >=20 > > That's closely related > > to the knapsack problem, and likewise NP-complete. It's probably a > > small enough example that it's tractable to solve, but that's > > *definitely* more trouble than it's worth. > >=20 > > [0] https://en.wikipedia.org/wiki/Multiple_subset_sum > >=20 > > [1] . In looking at this I accidentally went down a > > rabbit hole of a bunch of related optimization problems: the > > knapsack problem, multiple subset sum problem, bin packing > > problem. Ours isn't _quite_ the same as any of them, because we > > have a slightly different goal: we just want to see if there's any > > way we can fit everything in our 2 bins, not necessarily exactly > > fill bins or minimise number of bins. >=20 > To be picky, we would also like to minimise the number of bins (but > that could be done in a trivial way when possible), because we might > need to use 'file' as such. Right. So, the bin-packing problem aims for that, but it's typically set up with equally sized bins, which is not our case. >=20 > > I suspect, but I'm not sure, > > that this might allow it to be reduced to two instances of the > > (single) subset sum problem, each of which can be solved in > > O(#options * size of field we're packing)[2]. So maybe not > > actually NP-complete, still way more trouble than it's worth. >=20 > I'm under the impression that this could still qualify as the max-sum > variant of the multiple subset sum problem (assuming it helps), because > trying to fit all the options is also achieved by maximising the sum > (even though it's a somewhat different goal). Oh, it definitely qualifies as max-sum multiple subset sum (with m=3D2). I'm saying this specific case might also qualify as an easier problem that's not NP-complete. The trick is that the single maximum subset sum problem adits solutions bounded by the _minimum_ of the number of items to pack (number of options) and the target sum. For us that target sum is fixed to a not huge value. > > [2] https://www.geeksforgeeks.org/dsa/subset-sum-problem-dp-25/ > >=20 > > I still think "fill sname first" is the preferable option in practice. > > As well as leaving the file field free for the boot file, I suspect > > (but I'm not certain) it will result in better packing more often than > > not. > >=20 > > > > > + */ > > > > > + if (!(overload & DHCP_OVERLOAD_FILE) && > > > > > + opts[67].slen > 0 && (size_t)opts[67].slen < sizeof(reply.f= ile)) > > > > > + memcpy(&reply.file, opts[67].s, opts[67].slen + 1); > > > > > =20 > > > > > if (m->flags & FLAG_BROADCAST) > > > > > dst =3D in4addr_broadcast; >=20 > --=20 > Stefano >=20 --=20 David Gibson (he or they) | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you, not the other way | around. http://www.ozlabs.org/~dgibson --xm6SnLtDVYLipK2b Content-Type: application/pgp-signature; name=signature.asc -----BEGIN PGP SIGNATURE----- iQIzBAEBCgAdFiEEO+dNsU4E3yXUXRK2zQJF27ox2GcFAmoeKkQACgkQzQJF27ox 2GfjOxAAkpDiRf+h0IvMvL8iiI3L96p9MFIoCG1Y3jpEfMb+DFSo8eYJMzVdtSsL V4YA+q8CxWR6sXJMA64DE3wWHzmeg26qeAdTRTPB5+mPEKD/+tSKGg/oWyiHaAeY KFUBpUQzPf6UDN9l5zkhWBZBuhlfpRNXnUFwytVzC04pGLAbNf4juPU1926y69fa b89+2nTpv3tAv9v488gv8ljzePo2wvejtRy/GU6xB7k6ujhKGJm2iSTAzpRiDt/m exp3Hs+G6uUPQ6/es4CR+h8ywHTJEK5KUG+r8qiYRpka2KE+Km1RPdcUuy0m9jMT uyZiYTsTIIHHuxQUgCKtwg2tPtN5uiT6PetOo2f6wGhvgPf8QjK8bMm47fbhX7qJ xIboLAHOpVEggOBylzjs6wBUwfKiIWoOThIN23lbUVaggTAHOxUo6xIS/vPaHZuX /mnpUJwtOpBU2kVXDyrr3EKVFuFYxk8RwAlZxUi+pPwWYb9WX4L+YjHny8s107mY ldDdT3N6LLf+Hctxuj8+2clRDPWLA+AwDOCFm2eAiB0CIyzM8FbCKrL6K/f1zTht rYuVvHQAoV0vIPJAsc+q4M+T0a/K6sdJbZ1xVhMZJa6qqN47IGdXghCr5x+XH4lB VF82urlOhpVhV8a7REZHSpMdA+i6KrTv9d1AR5Jvo+vo7pw+rzE= =4Eol -----END PGP SIGNATURE----- --xm6SnLtDVYLipK2b--