Re: [PATCH v2 5/6] dhcp: Add option overload

[David Gibson <david@gibson.dropbear.id.au>]

[-- Attachment #1: Type: text/plain, Size: 12412 bytes --]

On Fri, May 29, 2026 at 09:00:19AM +0200, Stefano Brivio wrote:
> On Fri, 29 May 2026 15:49:49 +1000
> David Gibson <david@gibson.dropbear.id.au> 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 <david@gibson.dropbear.id.au> 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 <anskuma@redhat.com>
> > > > > ---
> > > > > 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] <huge tangent>.  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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]