From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: passt.top; dmarc=pass (p=quarantine dis=none) header.from=redhat.com Authentication-Results: passt.top; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=CFTKSMtv; dkim-atps=neutral Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by passt.top (Postfix) with ESMTPS id 6A49D5A026D for ; Fri, 29 May 2026 09:00:28 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1780038027; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Vf+f+FTHY5i86Aa8cZvBRfvkmePZHQOuRxdSnLx7dTw=; b=CFTKSMtv0YPt7n8KXEpWphHsI0B7/gisWnsaRJsWWMZuqg9cqQA2B7lbIqMvvExSH3AJ4e 4y3c+96K/nJHGyW9EELeN2qxAKyp07zmb+4wn4Fn7/mHe06jXUWWwoBVBH2i09Q4wTRIzk Kj21YWhfBvMb+e126d6/rPheAQd6KYM= Received: from mail-wr1-f69.google.com (mail-wr1-f69.google.com [209.85.221.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-57-xU_WWGrgMTGsral6vqf-Mg-1; Fri, 29 May 2026 03:00:24 -0400 X-MC-Unique: xU_WWGrgMTGsral6vqf-Mg-1 X-Mimecast-MFC-AGG-ID: xU_WWGrgMTGsral6vqf-Mg_1780038023 Received: by mail-wr1-f69.google.com with SMTP id ffacd0b85a97d-43d7730e9e3so8188413f8f.2 for ; Fri, 29 May 2026 00:00:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1780038023; x=1780642823; h=date:content-transfer-encoding:mime-version:organization:references :in-reply-to:message-id:subject:cc:to:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=RbVWsYGaBb1gjApTWbEKeqO9t0Ig06ICevwmEvyoyq0=; b=GKyi74CsTXy4wdbCRj2GNs75/S+thceliHTsZ4vHJLyspJ5heJJhC76riApoGRxaga b7Q0ss+w7nejILzDs7ZwxcdN28or9OkYEsct/kXg7v8QK+vDOj6E2BfkV9K7lKxJFoZC xz5gRiYbnwrKghHM7V4W3bu02CEEXsZCdv/kGlZ3D5y0L+9RhfSp7+ya7E9a5kdvGZEB QvN0pPxz22ifJZ7s9eXvb536FeP6GuZ1yRsCHILr3Do++HMRyVxH16tTQok+Ni9bnIrG iLBIkbvck3gBtUs4jeBETOlvbgolNXokVsCIjnCj6wsfFgB3l1apTx6kkbqbz1vpt1Tf RrfA== X-Forwarded-Encrypted: i=1; AFNElJ8q+A7Fhqiyu2MMqzS3Eg1VcvMfvaae1Sp+zPgx+qmfvwLoEVpld62vH2PaDC8JSZMAWTvNCF2gXHA=@passt.top X-Gm-Message-State: AOJu0YyaLpvqY92wkLnEkSjLZl5Z7ekArTyajYBsqFb+72e+l35z2SSt C8juUZPyvGC9+LWWODd3oyQWKy+/GtqsZnvVK5FcC0wz+Jq+muKy+BuNa/zHTkfGp2knUJipVM8 08CJFtMli8BgP2mCCTk+hjGpF1143DpCkZJOkNgXoBdRwhN5GU0oveg== X-Gm-Gg: Acq92OGdSpllDw6S+x/+nnXp3H1vNXIKlqWb0UG0t9P1XUt/sd1U+H/go4ex0lPBv16 Su5nF0ORgYTGeXV+3jWTZNl2AJQRbg0NlJ8LVv1ybKQHMufz3laPI4gLk6coArfdrJ30KU5CgKk +rj4igRHfWUiimQUdUIWfI93Qhw8PhixBh08WFP/T6I3GnqiHhAyTWxVVNs13bxtB9tuv7vKoSq p7LZVcuFc0MIUf2lF1RRmqDquD7yh7iiF7WNrZoAHJT/WFeZwCLSZgsflFd+7OsrZpQeI0/WzcN tDozMAx84nhi2pg4dzib/PZvcmAxAfBm/K9g8E4UKUUI5eCOa7hiT3YpPqpzW4e97G6L6ud+reQ YXi/gdoMLvEahLeqm/R6fLkC0j2DtLDuDL+GmTzfjs74= X-Received: by 2002:a05:6000:618:b0:452:273:5cd6 with SMTP id ffacd0b85a97d-45ef13ee98amr2731957f8f.1.1780038022272; Fri, 29 May 2026 00:00:22 -0700 (PDT) X-Received: by 2002:a05:6000:618:b0:452:273:5cd6 with SMTP id ffacd0b85a97d-45ef13ee98amr2731700f8f.1.1780038020629; Fri, 29 May 2026 00:00:20 -0700 (PDT) Received: from maya.myfinge.rs (ifcgrfdd.trafficplex.cloud. [2a10:fc81:a806:d6a9::1]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-45ef354cf0dsm1356189f8f.17.2026.05.29.00.00.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 29 May 2026 00:00:19 -0700 (PDT) From: Stefano Brivio To: David Gibson Subject: Re: [PATCH v2 5/6] dhcp: Add option overload Message-ID: <20260529090018.32e6d83a@elisabeth> In-Reply-To: References: <20260526123115.1226166-1-anskuma@redhat.com> <20260526123115.1226166-6-anskuma@redhat.com> <20260528210152.738a54df@elisabeth> Organization: Red Hat X-Mailer: Claws Mail 4.2.0 (GTK 3.24.49; x86_64-pc-linux-gnu) MIME-Version: 1.0 Date: Fri, 29 May 2026 09:00:19 +0200 (CEST) X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: 3fsH06AnGLcdwFrugE5-I2hvfj3MyGv0RV8-L1I9kyI_1780038023 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Message-ID-Hash: HQCTZV5XO6UNFVXV5EBVOWLLUMU7TD5Y X-Message-ID-Hash: HQCTZV5XO6UNFVXV5EBVOWLLUMU7TD5Y X-MailFrom: sbrivio@redhat.com 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: On Fri, 29 May 2026 15:49:49 +1000 David Gibson wrote: > 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 fit = in > > > > existing buffer, So when the options field is full, overflow remain= ing > > > > DHCP options into the file and sname fields per RFC 2132 option 52. > > > >=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_SNAM= E constants > > > > - Added comment documenting space reservation: /* Reserve 3 bytes= for option 52 */ > > > > - Fixed DNS search length: sizeof(m->o) only, not combined with f= ile+sname > > > > - Removed dhcp_boot references =E2=80=94 reply.file copy now read= s 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 siz= e, int o, int *offset) > > > > =09return false; > > > > } > > > > =20 > > > > +#define DHCP_OVERLOAD_FILE=091 > > > > +#define DHCP_OVERLOAD_SNAME=092 =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 fi= elds > > > > + * @m:=09=09Message whose file/sname fields may be used for overfl= ow > > > > + * > > > > + * Return: option 52 overload value: 0 if no overflow, > > > > + * DHCP_OVERLOAD_FILE for file, DHCP_OVERLOAD_SNAME for sn= ame, > > > > + * or both OR'd together > > > > + */ > > > > +static int fill_overflow(struct msg *m) > > > > +{ > > > > +=09int file_off =3D 0, sname_off =3D 0, overload =3D 0; > > > > +=09int o; > > > > + > > > > +=09for (o =3D 0; o < 255; o++) { =20 > > >=20 > > > You could use ARRAY_size(opts) instead of raw 255, yes? > > > =20 > > > > +=09=09if (opts[o].slen =3D=3D -1 || opts[o].sent) > > > > +=09=09=09continue; > > > > +=09=09fill_one(m->file, sizeof(m->file) - 1, o, &file_off); > > > > +=09} > > > > + > > > > +=09for (o =3D 0; o < 255; o++) { > > > > +=09=09if (opts[o].slen =3D=3D -1 || opts[o].sent) > > > > +=09=09=09continue; > > > > +=09=09if (fill_one(m->sname, sizeof(m->sname) - 1, o, &sname_off)) > > > > +=09=09=09debug("DHCP: skipping option %i (overload full)", o); > > > > +=09} > > > > + > > > > +=09if (file_off) { > > > > +=09=09m->file[file_off] =3D 255; > > > > +=09=09overload |=3D DHCP_OVERLOAD_FILE; > > > > +=09} > > > > + > > > > +=09if (sname_off) { > > > > +=09=09m->sname[sname_off] =3D 255; > > > > +=09=09overload |=3D DHCP_OVERLOAD_SNAME; > > > > +=09} > > > > + > > > > +=09return overload; > > > > +} > > > > + > > > > /** > > > > - * fill() - Fill options in message > > > > + * fill() - Fill options in message, with overload into file/sname= if needed > > > > * @m:=09=09Message to fill > > > > + * @overload:=09Set 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) > > > > { > > > > +=09/* Reserve 3 bytes for option 52 (overload) if needed */ > > > > +=09size_t size =3D OPT_MAX - 3; > > > > =09int i, o, offset =3D 0; > > > > =20 > > > > =09for (o =3D 0; o < 255; o++) > > > > @@ -324,20 +369,25 @@ static int fill(struct msg *m) > > > > =09 * Put it there explicitly, unless requested via option 55. > > > > =09 */ > > > > =09if (opts[55].clen > 0 && !memchr(opts[55].c, 53, opts[55].clen)= ) > > > > -=09=09if (fill_one(m->o, OPT_MAX, 53, &offset)) > > > > -=09=09=09 debug("DHCP: skipping option 53"); > > > > +=09=09fill_one(m->o, size, 53, &offset); > > > > =20 > > > > =09for (i =3D 0; i < opts[55].clen; i++) { > > > > =09=09o =3D opts[55].c[i]; > > > > =09=09if (opts[o].slen !=3D -1) > > > > -=09=09=09if (fill_one(m->o, OPT_MAX, o, &offset)) > > > > -=09=09=09=09debug("DHCP: skipping option %i", o); > > > > +=09=09=09fill_one(m->o, size, o, &offset); > > > > =09} > > > > =20 > > > > =09for (o =3D 0; o < 255; o++) { > > > > =09=09if (opts[o].slen !=3D -1 && !opts[o].sent) > > > > -=09=09=09if (fill_one(m->o, OPT_MAX, o, &offset)) > > > > -=09=09=09=09debug("DHCP: skipping option %i", o); > > > > +=09=09=09fill_one(m->o, size, o, &offset); > > > > +=09} > > > > + > > > > +=09*overload =3D fill_overflow(m); > > > > + > > > > +=09if (*overload) { > > > > +=09=09m->o[offset++] =3D 52; > > > > +=09=09m->o[offset++] =3D 1; > > > > +=09=09m->o[offset++] =3D *overload; > > > > =09} > > > > =20 > > > > =09m->o[offset++] =3D 255; > > > > @@ -462,6 +512,7 @@ int dhcp(const struct ctx *c, struct iov_tail *= data) > > > > =09struct msg const *m; > > > > =09struct msg reply; > > > > =09unsigned int i; > > > > +=09int overload; > > > > =20 > > > > =09eh =3D IOV_REMOVE_HEADER(data, eh_storage); > > > > =09iph =3D IOV_PEEK_HEADER(data, iph_storage); > > > > @@ -613,7 +664,22 @@ int dhcp(const struct ctx *c, struct iov_tail = *data) > > > > =09if (!c->no_dhcp_dns_search) > > > > =09=09opt_set_dns_search(c, sizeof(m->o)); > > > > =20 > > > > -=09dlen =3D offsetof(struct msg, o) + fill(&reply); > > > > +=09for (i =3D 0; i < (unsigned int)c->custom_opts_count; i++) { > > > > +=09=09uint8_t code =3D c->custom_opts[i].code; > > > > + > > > > +=09=09opts[code].slen =3D c->custom_opts[i].len; > > > > +=09=09memcpy(opts[code].s, c->custom_opts[i].val, > > > > +=09=09 c->custom_opts[i].len); > > > > +=09} > > > > + > > > > +=09dlen =3D offsetof(struct msg, o) + fill(&reply, &overload); > > > > + > > > > +=09/* Copy boot file name into the file field for legacy PXE clien= ts, > > > > +=09 * 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. Hmm, no, why? Note that Anshu's fill_overflow() loops on all (remaining) options for both fields, so in that case you would have: - 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 - 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 > 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. It's already done in some sense. 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. > Even that approach isn't theoretically optimal. This is (almost[1]) > the multiple subset sum problem for m=3D2 [0]. Right! Thanks, that's the one I meant. > 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. 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. > 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. 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). > [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 > > > > +=09 */ > > > > +=09if (!(overload & DHCP_OVERLOAD_FILE) && > > > > +=09 opts[67].slen > 0 && (size_t)opts[67].slen < sizeof(reply.f= ile)) > > > > +=09=09memcpy(&reply.file, opts[67].s, opts[67].slen + 1); > > > > =20 > > > > =09if (m->flags & FLAG_BROADCAST) > > > > =09=09dst =3D in4addr_broadcast; --=20 Stefano