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: > > > 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: > > > > > > > On Tue, May 26, 2026 at 06:01:12PM +0530, Anshu Kumari wrote: > > > > > 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 remaining > > > > > DHCP options into the file and sname fields per RFC 2132 option 52. > > > > > > > > > > Also, when the file field is not used for overload, copy the boot > > > > > file URL there directly for legacy PXE clients. > > > > > > > > > > Link: https://bugs.passt.top/show_bug.cgi?id=192 > > > > > Signed-off-by: Anshu Kumari > > > > > --- > > > > > v2: > > > > > - Added #define DHCP_OVERLOAD_FILE and #define DHCP_OVERLOAD_SNAME constants > > > > > - Added comment documenting space reservation: /* Reserve 3 bytes for option 52 */ > > > > > - Fixed DNS search length: sizeof(m->o) only, not combined with file+sname > > > > > - Removed dhcp_boot references — reply.file copy now reads from opts[67] > > > > > - Used DHCP_OVERLOAD_FILE constant in reply.file guard > > > > > --- > > > > > dhcp.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++------- > > > > > 1 file changed, 75 insertions(+), 9 deletions(-) > > > > > > > > > > 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 size, int o, int *offset) > > > > > return false; > > > > > } > > > > > > > > > > +#define DHCP_OVERLOAD_FILE 1 > > > > > +#define DHCP_OVERLOAD_SNAME 2 > > > > > > > > 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. > > > > > > > > > + > > > > > +/** > > > > > + * 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 = 0, sname_off = 0, overload = 0; > > > > > + int o; > > > > > + > > > > > + for (o = 0; o < 255; o++) { > > > > > > > > You could use ARRAY_size(opts) instead of raw 255, yes? > > > > > > > > > + if (opts[o].slen == -1 || opts[o].sent) > > > > > + continue; > > > > > + fill_one(m->file, sizeof(m->file) - 1, o, &file_off); > > > > > + } > > > > > + > > > > > + for (o = 0; o < 255; o++) { > > > > > + if (opts[o].slen == -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] = 255; > > > > > + overload |= DHCP_OVERLOAD_FILE; > > > > > + } > > > > > + > > > > > + if (sname_off) { > > > > > + m->sname[sname_off] = 255; > > > > > + overload |= DHCP_OVERLOAD_SNAME; > > > > > + } > > > > > + > > > > > + return overload; > > > > > +} > > > > > + > > > > > /** > > > > > - * fill() - Fill options in message > > > > > + * fill() - Fill options in message, with overload into file/sname if needed > > > > > * @m: Message to fill > > > > > + * @overload: Set to option 52 value (0 if none, 1/2/3 per RFC 2132) > > > > > * > > > > > * 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 = OPT_MAX - 3; > > > > > int i, o, offset = 0; > > > > > > > > > > for (o = 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); > > > > > > > > > > for (i = 0; i < opts[55].clen; i++) { > > > > > o = opts[55].c[i]; > > > > > if (opts[o].slen != -1) > > > > > - if (fill_one(m->o, OPT_MAX, o, &offset)) > > > > > - debug("DHCP: skipping option %i", o); > > > > > + fill_one(m->o, size, o, &offset); > > > > > } > > > > > > > > > > for (o = 0; o < 255; o++) { > > > > > if (opts[o].slen != -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 = fill_overflow(m); > > > > > + > > > > > + if (*overload) { > > > > > + m->o[offset++] = 52; > > > > > + m->o[offset++] = 1; > > > > > + m->o[offset++] = *overload; > > > > > } > > > > > > > > > > m->o[offset++] = 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; > > > > > > > > > > eh = IOV_REMOVE_HEADER(data, eh_storage); > > > > > iph = IOV_PEEK_HEADER(data, iph_storage); > > > > > @@ -613,7 +664,22 @@ int dhcp(const struct ctx *c, struct iov_tail *data) > > > > > if (!c->no_dhcp_dns_search) > > > > > opt_set_dns_search(c, sizeof(m->o)); > > > > > > > > > > - dlen = offsetof(struct msg, o) + fill(&reply); > > > > > + for (i = 0; i < (unsigned int)c->custom_opts_count; i++) { > > > > > + uint8_t code = c->custom_opts[i].code; > > > > > + > > > > > + opts[code].slen = c->custom_opts[i].len; > > > > > + memcpy(opts[code].s, c->custom_opts[i].val, > > > > > + c->custom_opts[i].len); > > > > > + } > > > > > + > > > > > + dlen = offsetof(struct msg, o) + fill(&reply, &overload); > > > > > + > > > > > + /* Copy boot file name into the file field for legacy PXE clients, > > > > > + * unless the file field is already used for option overload. > > > > > > > > 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, > > > > > > 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. > > > > > > If we try sname (smaller) first, we *should* have strictly better > > > chances than the other way around. > > > > > > Example: we need to fit (hypothetical) options 20 (20 bytes), option 30 > > > (30 bytes) and option 120 (120 bytes). If we try 'file' first: > > > > > > - option 20 fits, option 30 fits, nothing else, move to 'sname' > > > - nothing else fits: two options encoded > > > > > > If we try 'sname' first: > > > > > > - option 20 fits, option 30 fits, nothing else, move to 'file' > > > - option 120 fits: three options encoded > > > > > > There must be some relatively simple proof or theorem for this but > > > right now I can't think of any name / reference. > > > > 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: 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 > > - 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. 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. > > > Even that approach isn't theoretically optimal. This is (almost[1]) > > the multiple subset sum problem for m=2 [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. > > > > [0] https://en.wikipedia.org/wiki/Multiple_subset_sum > > > > [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. Right. So, the bin-packing problem aims for that, but it's typically set up with equally sized bins, which is not our case. > > > 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). Oh, it definitely qualifies as max-sum multiple subset sum (with m=2). 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/ > > > > 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. > > > > > > > + */ > > > > > + if (!(overload & DHCP_OVERLOAD_FILE) && > > > > > + opts[67].slen > 0 && (size_t)opts[67].slen < sizeof(reply.file)) > > > > > + memcpy(&reply.file, opts[67].s, opts[67].slen + 1); > > > > > > > > > > if (m->flags & FLAG_BROADCAST) > > > > > dst = in4addr_broadcast; > > -- > Stefano > -- 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