uipc_mbuf.c revision 130289
1/*
2 * Copyright (c) 1982, 1986, 1988, 1991, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 * 4. Neither the name of the University nor the names of its contributors
14 *    may be used to endorse or promote products derived from this software
15 *    without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 *	@(#)uipc_mbuf.c	8.2 (Berkeley) 1/4/94
30 */
31
32#include <sys/cdefs.h>
33__FBSDID("$FreeBSD: head/sys/kern/uipc_mbuf.c 130289 2004-06-10 00:04:27Z bmilekic $");
34
35#include "opt_mac.h"
36#include "opt_param.h"
37#include "opt_mbuf_stress_test.h"
38
39#include <sys/param.h>
40#include <sys/systm.h>
41#include <sys/kernel.h>
42#include <sys/limits.h>
43#include <sys/lock.h>
44#include <sys/mac.h>
45#include <sys/malloc.h>
46#include <sys/mbuf.h>
47#include <sys/sysctl.h>
48#include <sys/domain.h>
49#include <sys/protosw.h>
50#include <sys/uio.h>
51
52int	max_linkhdr;
53int	max_protohdr;
54int	max_hdr;
55int	max_datalen;
56#ifdef MBUF_STRESS_TEST
57int	m_defragpackets;
58int	m_defragbytes;
59int	m_defraguseless;
60int	m_defragfailure;
61int	m_defragrandomfailures;
62#endif
63
64/*
65 * sysctl(8) exported objects
66 */
67SYSCTL_DECL(_kern_ipc);
68SYSCTL_INT(_kern_ipc, KIPC_MAX_LINKHDR, max_linkhdr, CTLFLAG_RW,
69	   &max_linkhdr, 0, "");
70SYSCTL_INT(_kern_ipc, KIPC_MAX_PROTOHDR, max_protohdr, CTLFLAG_RW,
71	   &max_protohdr, 0, "");
72SYSCTL_INT(_kern_ipc, KIPC_MAX_HDR, max_hdr, CTLFLAG_RW, &max_hdr, 0, "");
73SYSCTL_INT(_kern_ipc, KIPC_MAX_DATALEN, max_datalen, CTLFLAG_RW,
74	   &max_datalen, 0, "");
75#ifdef MBUF_STRESS_TEST
76SYSCTL_INT(_kern_ipc, OID_AUTO, m_defragpackets, CTLFLAG_RD,
77	   &m_defragpackets, 0, "");
78SYSCTL_INT(_kern_ipc, OID_AUTO, m_defragbytes, CTLFLAG_RD,
79	   &m_defragbytes, 0, "");
80SYSCTL_INT(_kern_ipc, OID_AUTO, m_defraguseless, CTLFLAG_RD,
81	   &m_defraguseless, 0, "");
82SYSCTL_INT(_kern_ipc, OID_AUTO, m_defragfailure, CTLFLAG_RD,
83	   &m_defragfailure, 0, "");
84SYSCTL_INT(_kern_ipc, OID_AUTO, m_defragrandomfailures, CTLFLAG_RW,
85	   &m_defragrandomfailures, 0, "");
86#endif
87
88/*
89 * Malloc-type for external ext_buf ref counts.
90 */
91MALLOC_DEFINE(M_MBUF, "mbextcnt", "mbuf external ref counts");
92
93/*
94 * Allocate a given length worth of mbufs and/or clusters (whatever fits
95 * best) and return a pointer to the top of the allocated chain.  If an
96 * existing mbuf chain is provided, then we will append the new chain
97 * to the existing one but still return the top of the newly allocated
98 * chain.
99 */
100struct mbuf *
101m_getm(struct mbuf *m, int len, int how, short type)
102{
103	struct mbuf *mb, *top, *cur, *mtail;
104	int num, rem;
105	int i;
106
107	KASSERT(len >= 0, ("m_getm(): len is < 0"));
108
109	/* If m != NULL, we will append to the end of that chain. */
110	if (m != NULL)
111		for (mtail = m; mtail->m_next != NULL; mtail = mtail->m_next);
112	else
113		mtail = NULL;
114
115	/*
116	 * Calculate how many mbufs+clusters ("packets") we need and how much
117	 * leftover there is after that and allocate the first mbuf+cluster
118	 * if required.
119	 */
120	num = len / MCLBYTES;
121	rem = len % MCLBYTES;
122	top = cur = NULL;
123	if (num > 0) {
124		if ((top = cur = m_getcl(how, type, 0)) == NULL)
125			goto failed;
126		top->m_len = 0;
127	}
128	num--;
129
130	for (i = 0; i < num; i++) {
131		mb = m_getcl(how, type, 0);
132		if (mb == NULL)
133			goto failed;
134		mb->m_len = 0;
135		cur = (cur->m_next = mb);
136	}
137	if (rem > 0) {
138		mb = (rem > MINCLSIZE) ?
139		    m_getcl(how, type, 0) : m_get(how, type);
140		if (mb == NULL)
141			goto failed;
142		mb->m_len = 0;
143		if (cur == NULL)
144			top = mb;
145		else
146			cur->m_next = mb;
147	}
148
149	if (mtail != NULL)
150		mtail->m_next = top;
151	return top;
152failed:
153	if (top != NULL)
154		m_freem(top);
155	return NULL;
156}
157
158/*
159 * Free an entire chain of mbufs and associated external buffers, if
160 * applicable.
161 */
162void
163m_freem(struct mbuf *mb)
164{
165
166	while (mb != NULL)
167		mb = m_free(mb);
168}
169
170/*-
171 * Configure a provided mbuf to refer to the provided external storage
172 * buffer and setup a reference count for said buffer.  If the setting
173 * up of the reference count fails, the M_EXT bit will not be set.  If
174 * successfull, the M_EXT bit is set in the mbuf's flags.
175 *
176 * Arguments:
177 *    mb     The existing mbuf to which to attach the provided buffer.
178 *    buf    The address of the provided external storage buffer.
179 *    size   The size of the provided buffer.
180 *    freef  A pointer to a routine that is responsible for freeing the
181 *           provided external storage buffer.
182 *    args   A pointer to an argument structure (of any type) to be passed
183 *           to the provided freef routine (may be NULL).
184 *    flags  Any other flags to be passed to the provided mbuf.
185 *    type   The type that the external storage buffer should be
186 *           labeled with.
187 *
188 * Returns:
189 *    Nothing.
190 */
191void
192m_extadd(struct mbuf *mb, caddr_t buf, u_int size,
193    void (*freef)(void *, void *), void *args, int flags, int type)
194{
195	u_int *ref_cnt = NULL;
196
197	/* XXX Shouldn't be adding EXT_CLUSTER with this API */
198	if (type == EXT_CLUSTER)
199		ref_cnt = (u_int *)uma_find_refcnt(zone_clust,
200		    mb->m_ext.ext_buf);
201	else if (type == EXT_EXTREF)
202		ref_cnt = mb->m_ext.ref_cnt;
203	mb->m_ext.ref_cnt = (ref_cnt == NULL) ?
204	    malloc(sizeof(u_int), M_MBUF, M_NOWAIT) : (u_int *)ref_cnt;
205	if (mb->m_ext.ref_cnt != NULL) {
206		*(mb->m_ext.ref_cnt) = 1;
207		mb->m_flags |= (M_EXT | flags);
208		mb->m_ext.ext_buf = buf;
209		mb->m_data = mb->m_ext.ext_buf;
210		mb->m_ext.ext_size = size;
211		mb->m_ext.ext_free = freef;
212		mb->m_ext.ext_args = args;
213		mb->m_ext.ext_type = type;
214        }
215}
216
217/*
218 * Non-directly-exported function to clean up after mbufs with M_EXT
219 * storage attached to them if the reference count hits 0.
220 */
221void
222mb_free_ext(struct mbuf *m)
223{
224	u_int cnt;
225
226	/*
227	 * This is tricky.  We need to make sure to decrement the
228	 * refcount in a safe way but to also clean up if we're the
229	 * last reference.  This method seems to do it without race.
230	 */
231	do {
232		cnt = *(m->m_ext.ref_cnt);
233		if (atomic_cmpset_int(m->m_ext.ref_cnt, cnt, cnt - 1)) {
234			if (cnt == 1) {
235				/*
236				 * Do the free, should be safe.
237				 */
238				if (m->m_ext.ext_type == EXT_PACKET) {
239					uma_zfree(zone_pack, m);
240					break;
241				} else if (m->m_ext.ext_type == EXT_CLUSTER) {
242					uma_zfree(zone_clust, m->m_ext.ext_buf);
243					m->m_ext.ext_buf = NULL;
244				} else {
245					(*(m->m_ext.ext_free))(m->m_ext.ext_buf,
246					    m->m_ext.ext_args);
247					if (m->m_ext.ext_type != EXT_EXTREF)
248						free(m->m_ext.ref_cnt, M_MBUF);
249				}
250				uma_zfree(zone_mbuf, m);
251			}
252			/* Decrement (and potentially free) done, safely. */
253			break;
254		}
255	} while (1);
256}
257
258/*
259 * "Move" mbuf pkthdr from "from" to "to".
260 * "from" must have M_PKTHDR set, and "to" must be empty.
261 */
262void
263m_move_pkthdr(struct mbuf *to, struct mbuf *from)
264{
265
266#if 0
267	/* see below for why these are not enabled */
268	M_ASSERTPKTHDR(to);
269	/* Note: with MAC, this may not be a good assertion. */
270	KASSERT(SLIST_EMPTY(&to->m_pkthdr.tags),
271	    ("m_move_pkthdr: to has tags"));
272#endif
273	KASSERT((to->m_flags & M_EXT) == 0, ("m_move_pkthdr: to has cluster"));
274#ifdef MAC
275	/*
276	 * XXXMAC: It could be this should also occur for non-MAC?
277	 */
278	if (to->m_flags & M_PKTHDR)
279		m_tag_delete_chain(to, NULL);
280#endif
281	to->m_flags = from->m_flags & M_COPYFLAGS;
282	to->m_data = to->m_pktdat;
283	to->m_pkthdr = from->m_pkthdr;		/* especially tags */
284	SLIST_INIT(&from->m_pkthdr.tags);	/* purge tags from src */
285	from->m_flags &= ~M_PKTHDR;
286}
287
288/*
289 * Duplicate "from"'s mbuf pkthdr in "to".
290 * "from" must have M_PKTHDR set, and "to" must be empty.
291 * In particular, this does a deep copy of the packet tags.
292 */
293int
294m_dup_pkthdr(struct mbuf *to, struct mbuf *from, int how)
295{
296
297#if 0
298	/*
299	 * The mbuf allocator only initializes the pkthdr
300	 * when the mbuf is allocated with MGETHDR. Many users
301	 * (e.g. m_copy*, m_prepend) use MGET and then
302	 * smash the pkthdr as needed causing these
303	 * assertions to trip.  For now just disable them.
304	 */
305	M_ASSERTPKTHDR(to);
306	/* Note: with MAC, this may not be a good assertion. */
307	KASSERT(SLIST_EMPTY(&to->m_pkthdr.tags), ("m_dup_pkthdr: to has tags"));
308#endif
309#ifdef MAC
310	if (to->m_flags & M_PKTHDR)
311		m_tag_delete_chain(to, NULL);
312#endif
313	to->m_flags = (from->m_flags & M_COPYFLAGS) | (to->m_flags & M_EXT);
314	if ((to->m_flags & M_EXT) == 0)
315		to->m_data = to->m_pktdat;
316	to->m_pkthdr = from->m_pkthdr;
317	SLIST_INIT(&to->m_pkthdr.tags);
318	return (m_tag_copy_chain(to, from, MBTOM(how)));
319}
320
321/*
322 * Lesser-used path for M_PREPEND:
323 * allocate new mbuf to prepend to chain,
324 * copy junk along.
325 */
326struct mbuf *
327m_prepend(struct mbuf *m, int len, int how)
328{
329	struct mbuf *mn;
330
331	if (m->m_flags & M_PKTHDR)
332		MGETHDR(mn, how, m->m_type);
333	else
334		MGET(mn, how, m->m_type);
335	if (mn == NULL) {
336		m_freem(m);
337		return (NULL);
338	}
339	if (m->m_flags & M_PKTHDR)
340		M_MOVE_PKTHDR(mn, m);
341	mn->m_next = m;
342	m = mn;
343	if (len < MHLEN)
344		MH_ALIGN(m, len);
345	m->m_len = len;
346	return (m);
347}
348
349/*
350 * Make a copy of an mbuf chain starting "off0" bytes from the beginning,
351 * continuing for "len" bytes.  If len is M_COPYALL, copy to end of mbuf.
352 * The wait parameter is a choice of M_TRYWAIT/M_DONTWAIT from caller.
353 * Note that the copy is read-only, because clusters are not copied,
354 * only their reference counts are incremented.
355 */
356struct mbuf *
357m_copym(struct mbuf *m, int off0, int len, int wait)
358{
359	struct mbuf *n, **np;
360	int off = off0;
361	struct mbuf *top;
362	int copyhdr = 0;
363
364	KASSERT(off >= 0, ("m_copym, negative off %d", off));
365	KASSERT(len >= 0, ("m_copym, negative len %d", len));
366	if (off == 0 && m->m_flags & M_PKTHDR)
367		copyhdr = 1;
368	while (off > 0) {
369		KASSERT(m != NULL, ("m_copym, offset > size of mbuf chain"));
370		if (off < m->m_len)
371			break;
372		off -= m->m_len;
373		m = m->m_next;
374	}
375	np = &top;
376	top = 0;
377	while (len > 0) {
378		if (m == NULL) {
379			KASSERT(len == M_COPYALL,
380			    ("m_copym, length > size of mbuf chain"));
381			break;
382		}
383		if (copyhdr)
384			MGETHDR(n, wait, m->m_type);
385		else
386			MGET(n, wait, m->m_type);
387		*np = n;
388		if (n == NULL)
389			goto nospace;
390		if (copyhdr) {
391			if (!m_dup_pkthdr(n, m, wait))
392				goto nospace;
393			if (len == M_COPYALL)
394				n->m_pkthdr.len -= off0;
395			else
396				n->m_pkthdr.len = len;
397			copyhdr = 0;
398		}
399		n->m_len = min(len, m->m_len - off);
400		if (m->m_flags & M_EXT) {
401			n->m_data = m->m_data + off;
402			n->m_ext = m->m_ext;
403			n->m_flags |= M_EXT;
404			MEXT_ADD_REF(m);
405		} else
406			bcopy(mtod(m, caddr_t)+off, mtod(n, caddr_t),
407			    (u_int)n->m_len);
408		if (len != M_COPYALL)
409			len -= n->m_len;
410		off = 0;
411		m = m->m_next;
412		np = &n->m_next;
413	}
414	if (top == NULL)
415		mbstat.m_mcfail++;	/* XXX: No consistency. */
416
417	return (top);
418nospace:
419	m_freem(top);
420	mbstat.m_mcfail++;	/* XXX: No consistency. */
421	return (NULL);
422}
423
424/*
425 * Copy an entire packet, including header (which must be present).
426 * An optimization of the common case `m_copym(m, 0, M_COPYALL, how)'.
427 * Note that the copy is read-only, because clusters are not copied,
428 * only their reference counts are incremented.
429 * Preserve alignment of the first mbuf so if the creator has left
430 * some room at the beginning (e.g. for inserting protocol headers)
431 * the copies still have the room available.
432 */
433struct mbuf *
434m_copypacket(struct mbuf *m, int how)
435{
436	struct mbuf *top, *n, *o;
437
438	MGET(n, how, m->m_type);
439	top = n;
440	if (n == NULL)
441		goto nospace;
442
443	if (!m_dup_pkthdr(n, m, how))
444		goto nospace;
445	n->m_len = m->m_len;
446	if (m->m_flags & M_EXT) {
447		n->m_data = m->m_data;
448		n->m_ext = m->m_ext;
449		n->m_flags |= M_EXT;
450		MEXT_ADD_REF(m);
451	} else {
452		n->m_data = n->m_pktdat + (m->m_data - m->m_pktdat );
453		bcopy(mtod(m, char *), mtod(n, char *), n->m_len);
454	}
455
456	m = m->m_next;
457	while (m) {
458		MGET(o, how, m->m_type);
459		if (o == NULL)
460			goto nospace;
461
462		n->m_next = o;
463		n = n->m_next;
464
465		n->m_len = m->m_len;
466		if (m->m_flags & M_EXT) {
467			n->m_data = m->m_data;
468			n->m_ext = m->m_ext;
469			n->m_flags |= M_EXT;
470			MEXT_ADD_REF(m);
471		} else {
472			bcopy(mtod(m, char *), mtod(n, char *), n->m_len);
473		}
474
475		m = m->m_next;
476	}
477	return top;
478nospace:
479	m_freem(top);
480	mbstat.m_mcfail++;	/* XXX: No consistency. */
481	return (NULL);
482}
483
484/*
485 * Copy data from an mbuf chain starting "off" bytes from the beginning,
486 * continuing for "len" bytes, into the indicated buffer.
487 */
488void
489m_copydata(const struct mbuf *m, int off, int len, caddr_t cp)
490{
491	u_int count;
492
493	KASSERT(off >= 0, ("m_copydata, negative off %d", off));
494	KASSERT(len >= 0, ("m_copydata, negative len %d", len));
495	while (off > 0) {
496		KASSERT(m != NULL, ("m_copydata, offset > size of mbuf chain"));
497		if (off < m->m_len)
498			break;
499		off -= m->m_len;
500		m = m->m_next;
501	}
502	while (len > 0) {
503		KASSERT(m != NULL, ("m_copydata, length > size of mbuf chain"));
504		count = min(m->m_len - off, len);
505		bcopy(mtod(m, caddr_t) + off, cp, count);
506		len -= count;
507		cp += count;
508		off = 0;
509		m = m->m_next;
510	}
511}
512
513/*
514 * Copy a packet header mbuf chain into a completely new chain, including
515 * copying any mbuf clusters.  Use this instead of m_copypacket() when
516 * you need a writable copy of an mbuf chain.
517 */
518struct mbuf *
519m_dup(struct mbuf *m, int how)
520{
521	struct mbuf **p, *top = NULL;
522	int remain, moff, nsize;
523
524	/* Sanity check */
525	if (m == NULL)
526		return (NULL);
527	M_ASSERTPKTHDR(m);
528
529	/* While there's more data, get a new mbuf, tack it on, and fill it */
530	remain = m->m_pkthdr.len;
531	moff = 0;
532	p = &top;
533	while (remain > 0 || top == NULL) {	/* allow m->m_pkthdr.len == 0 */
534		struct mbuf *n;
535
536		/* Get the next new mbuf */
537		if (remain >= MINCLSIZE) {
538			n = m_getcl(how, m->m_type, 0);
539			nsize = MCLBYTES;
540		} else {
541			n = m_get(how, m->m_type);
542			nsize = MLEN;
543		}
544		if (n == NULL)
545			goto nospace;
546
547		if (top == NULL) {		/* First one, must be PKTHDR */
548			if (!m_dup_pkthdr(n, m, how)) {
549				m_free(n);
550				goto nospace;
551			}
552			nsize = MHLEN;
553		}
554		n->m_len = 0;
555
556		/* Link it into the new chain */
557		*p = n;
558		p = &n->m_next;
559
560		/* Copy data from original mbuf(s) into new mbuf */
561		while (n->m_len < nsize && m != NULL) {
562			int chunk = min(nsize - n->m_len, m->m_len - moff);
563
564			bcopy(m->m_data + moff, n->m_data + n->m_len, chunk);
565			moff += chunk;
566			n->m_len += chunk;
567			remain -= chunk;
568			if (moff == m->m_len) {
569				m = m->m_next;
570				moff = 0;
571			}
572		}
573
574		/* Check correct total mbuf length */
575		KASSERT((remain > 0 && m != NULL) || (remain == 0 && m == NULL),
576		    	("%s: bogus m_pkthdr.len", __func__));
577	}
578	return (top);
579
580nospace:
581	m_freem(top);
582	mbstat.m_mcfail++;	/* XXX: No consistency. */
583	return (NULL);
584}
585
586/*
587 * Concatenate mbuf chain n to m.
588 * Both chains must be of the same type (e.g. MT_DATA).
589 * Any m_pkthdr is not updated.
590 */
591void
592m_cat(struct mbuf *m, struct mbuf *n)
593{
594	while (m->m_next)
595		m = m->m_next;
596	while (n) {
597		if (m->m_flags & M_EXT ||
598		    m->m_data + m->m_len + n->m_len >= &m->m_dat[MLEN]) {
599			/* just join the two chains */
600			m->m_next = n;
601			return;
602		}
603		/* splat the data from one into the other */
604		bcopy(mtod(n, caddr_t), mtod(m, caddr_t) + m->m_len,
605		    (u_int)n->m_len);
606		m->m_len += n->m_len;
607		n = m_free(n);
608	}
609}
610
611void
612m_adj(struct mbuf *mp, int req_len)
613{
614	int len = req_len;
615	struct mbuf *m;
616	int count;
617
618	if ((m = mp) == NULL)
619		return;
620	if (len >= 0) {
621		/*
622		 * Trim from head.
623		 */
624		while (m != NULL && len > 0) {
625			if (m->m_len <= len) {
626				len -= m->m_len;
627				m->m_len = 0;
628				m = m->m_next;
629			} else {
630				m->m_len -= len;
631				m->m_data += len;
632				len = 0;
633			}
634		}
635		m = mp;
636		if (mp->m_flags & M_PKTHDR)
637			m->m_pkthdr.len -= (req_len - len);
638	} else {
639		/*
640		 * Trim from tail.  Scan the mbuf chain,
641		 * calculating its length and finding the last mbuf.
642		 * If the adjustment only affects this mbuf, then just
643		 * adjust and return.  Otherwise, rescan and truncate
644		 * after the remaining size.
645		 */
646		len = -len;
647		count = 0;
648		for (;;) {
649			count += m->m_len;
650			if (m->m_next == (struct mbuf *)0)
651				break;
652			m = m->m_next;
653		}
654		if (m->m_len >= len) {
655			m->m_len -= len;
656			if (mp->m_flags & M_PKTHDR)
657				mp->m_pkthdr.len -= len;
658			return;
659		}
660		count -= len;
661		if (count < 0)
662			count = 0;
663		/*
664		 * Correct length for chain is "count".
665		 * Find the mbuf with last data, adjust its length,
666		 * and toss data from remaining mbufs on chain.
667		 */
668		m = mp;
669		if (m->m_flags & M_PKTHDR)
670			m->m_pkthdr.len = count;
671		for (; m; m = m->m_next) {
672			if (m->m_len >= count) {
673				m->m_len = count;
674				break;
675			}
676			count -= m->m_len;
677		}
678		while (m->m_next)
679			(m = m->m_next) ->m_len = 0;
680	}
681}
682
683/*
684 * Rearange an mbuf chain so that len bytes are contiguous
685 * and in the data area of an mbuf (so that mtod and dtom
686 * will work for a structure of size len).  Returns the resulting
687 * mbuf chain on success, frees it and returns null on failure.
688 * If there is room, it will add up to max_protohdr-len extra bytes to the
689 * contiguous region in an attempt to avoid being called next time.
690 */
691struct mbuf *
692m_pullup(struct mbuf *n, int len)
693{
694	struct mbuf *m;
695	int count;
696	int space;
697
698	/*
699	 * If first mbuf has no cluster, and has room for len bytes
700	 * without shifting current data, pullup into it,
701	 * otherwise allocate a new mbuf to prepend to the chain.
702	 */
703	if ((n->m_flags & M_EXT) == 0 &&
704	    n->m_data + len < &n->m_dat[MLEN] && n->m_next) {
705		if (n->m_len >= len)
706			return (n);
707		m = n;
708		n = n->m_next;
709		len -= m->m_len;
710	} else {
711		if (len > MHLEN)
712			goto bad;
713		MGET(m, M_DONTWAIT, n->m_type);
714		if (m == NULL)
715			goto bad;
716		m->m_len = 0;
717		if (n->m_flags & M_PKTHDR)
718			M_MOVE_PKTHDR(m, n);
719	}
720	space = &m->m_dat[MLEN] - (m->m_data + m->m_len);
721	do {
722		count = min(min(max(len, max_protohdr), space), n->m_len);
723		bcopy(mtod(n, caddr_t), mtod(m, caddr_t) + m->m_len,
724		  (u_int)count);
725		len -= count;
726		m->m_len += count;
727		n->m_len -= count;
728		space -= count;
729		if (n->m_len)
730			n->m_data += count;
731		else
732			n = m_free(n);
733	} while (len > 0 && n);
734	if (len > 0) {
735		(void) m_free(m);
736		goto bad;
737	}
738	m->m_next = n;
739	return (m);
740bad:
741	m_freem(n);
742	mbstat.m_mpfail++;	/* XXX: No consistency. */
743	return (NULL);
744}
745
746/*
747 * Partition an mbuf chain in two pieces, returning the tail --
748 * all but the first len0 bytes.  In case of failure, it returns NULL and
749 * attempts to restore the chain to its original state.
750 *
751 * Note that the resulting mbufs might be read-only, because the new
752 * mbuf can end up sharing an mbuf cluster with the original mbuf if
753 * the "breaking point" happens to lie within a cluster mbuf. Use the
754 * M_WRITABLE() macro to check for this case.
755 */
756struct mbuf *
757m_split(struct mbuf *m0, int len0, int wait)
758{
759	struct mbuf *m, *n;
760	u_int len = len0, remain;
761
762	for (m = m0; m && len > m->m_len; m = m->m_next)
763		len -= m->m_len;
764	if (m == NULL)
765		return (NULL);
766	remain = m->m_len - len;
767	if (m0->m_flags & M_PKTHDR) {
768		MGETHDR(n, wait, m0->m_type);
769		if (n == NULL)
770			return (NULL);
771		n->m_pkthdr.rcvif = m0->m_pkthdr.rcvif;
772		n->m_pkthdr.len = m0->m_pkthdr.len - len0;
773		m0->m_pkthdr.len = len0;
774		if (m->m_flags & M_EXT)
775			goto extpacket;
776		if (remain > MHLEN) {
777			/* m can't be the lead packet */
778			MH_ALIGN(n, 0);
779			n->m_next = m_split(m, len, wait);
780			if (n->m_next == NULL) {
781				(void) m_free(n);
782				return (NULL);
783			} else {
784				n->m_len = 0;
785				return (n);
786			}
787		} else
788			MH_ALIGN(n, remain);
789	} else if (remain == 0) {
790		n = m->m_next;
791		m->m_next = NULL;
792		return (n);
793	} else {
794		MGET(n, wait, m->m_type);
795		if (n == NULL)
796			return (NULL);
797		M_ALIGN(n, remain);
798	}
799extpacket:
800	if (m->m_flags & M_EXT) {
801		n->m_flags |= M_EXT;
802		n->m_ext = m->m_ext;
803		MEXT_ADD_REF(m);
804		n->m_data = m->m_data + len;
805	} else {
806		bcopy(mtod(m, caddr_t) + len, mtod(n, caddr_t), remain);
807	}
808	n->m_len = remain;
809	m->m_len = len;
810	n->m_next = m->m_next;
811	m->m_next = NULL;
812	return (n);
813}
814/*
815 * Routine to copy from device local memory into mbufs.
816 * Note that `off' argument is offset into first mbuf of target chain from
817 * which to begin copying the data to.
818 */
819struct mbuf *
820m_devget(char *buf, int totlen, int off, struct ifnet *ifp,
821	 void (*copy)(char *from, caddr_t to, u_int len))
822{
823	struct mbuf *m;
824	struct mbuf *top = NULL, **mp = &top;
825	int len;
826
827	if (off < 0 || off > MHLEN)
828		return (NULL);
829
830	while (totlen > 0) {
831		if (top == NULL) {	/* First one, must be PKTHDR */
832			if (totlen + off >= MINCLSIZE) {
833				m = m_getcl(M_DONTWAIT, MT_DATA, M_PKTHDR);
834				len = MCLBYTES;
835			} else {
836				m = m_gethdr(M_DONTWAIT, MT_DATA);
837				len = MHLEN;
838
839				/* Place initial small packet/header at end of mbuf */
840				if (m && totlen + off + max_linkhdr <= MLEN) {
841					m->m_data += max_linkhdr;
842					len -= max_linkhdr;
843				}
844			}
845			if (m == NULL)
846				return NULL;
847			m->m_pkthdr.rcvif = ifp;
848			m->m_pkthdr.len = totlen;
849		} else {
850			if (totlen + off >= MINCLSIZE) {
851				m = m_getcl(M_DONTWAIT, MT_DATA, 0);
852				len = MCLBYTES;
853			} else {
854				m = m_get(M_DONTWAIT, MT_DATA);
855				len = MLEN;
856			}
857			if (m == NULL) {
858				m_freem(top);
859				return NULL;
860			}
861		}
862		if (off) {
863			m->m_data += off;
864			len -= off;
865			off = 0;
866		}
867		m->m_len = len = min(totlen, len);
868		if (copy)
869			copy(buf, mtod(m, caddr_t), (u_int)len);
870		else
871			bcopy(buf, mtod(m, caddr_t), (u_int)len);
872		buf += len;
873		*mp = m;
874		mp = &m->m_next;
875		totlen -= len;
876	}
877	return (top);
878}
879
880/*
881 * Copy data from a buffer back into the indicated mbuf chain,
882 * starting "off" bytes from the beginning, extending the mbuf
883 * chain if necessary.
884 */
885void
886m_copyback(struct mbuf *m0, int off, int len, c_caddr_t cp)
887{
888	int mlen;
889	struct mbuf *m = m0, *n;
890	int totlen = 0;
891
892	if (m0 == NULL)
893		return;
894	while (off > (mlen = m->m_len)) {
895		off -= mlen;
896		totlen += mlen;
897		if (m->m_next == NULL) {
898			n = m_get(M_DONTWAIT, m->m_type);
899			if (n == NULL)
900				goto out;
901			bzero(mtod(n, caddr_t), MLEN);
902			n->m_len = min(MLEN, len + off);
903			m->m_next = n;
904		}
905		m = m->m_next;
906	}
907	while (len > 0) {
908		mlen = min (m->m_len - off, len);
909		bcopy(cp, off + mtod(m, caddr_t), (u_int)mlen);
910		cp += mlen;
911		len -= mlen;
912		mlen += off;
913		off = 0;
914		totlen += mlen;
915		if (len == 0)
916			break;
917		if (m->m_next == NULL) {
918			n = m_get(M_DONTWAIT, m->m_type);
919			if (n == NULL)
920				break;
921			n->m_len = min(MLEN, len);
922			m->m_next = n;
923		}
924		m = m->m_next;
925	}
926out:	if (((m = m0)->m_flags & M_PKTHDR) && (m->m_pkthdr.len < totlen))
927		m->m_pkthdr.len = totlen;
928}
929
930/*
931 * Apply function f to the data in an mbuf chain starting "off" bytes from
932 * the beginning, continuing for "len" bytes.
933 */
934int
935m_apply(struct mbuf *m, int off, int len,
936    int (*f)(void *, void *, u_int), void *arg)
937{
938	u_int count;
939	int rval;
940
941	KASSERT(off >= 0, ("m_apply, negative off %d", off));
942	KASSERT(len >= 0, ("m_apply, negative len %d", len));
943	while (off > 0) {
944		KASSERT(m != NULL, ("m_apply, offset > size of mbuf chain"));
945		if (off < m->m_len)
946			break;
947		off -= m->m_len;
948		m = m->m_next;
949	}
950	while (len > 0) {
951		KASSERT(m != NULL, ("m_apply, offset > size of mbuf chain"));
952		count = min(m->m_len - off, len);
953		rval = (*f)(arg, mtod(m, caddr_t) + off, count);
954		if (rval)
955			return (rval);
956		len -= count;
957		off = 0;
958		m = m->m_next;
959	}
960	return (0);
961}
962
963/*
964 * Return a pointer to mbuf/offset of location in mbuf chain.
965 */
966struct mbuf *
967m_getptr(struct mbuf *m, int loc, int *off)
968{
969
970	while (loc >= 0) {
971		/* Normal end of search. */
972		if (m->m_len > loc) {
973			*off = loc;
974			return (m);
975		} else {
976			loc -= m->m_len;
977			if (m->m_next == NULL) {
978				if (loc == 0) {
979					/* Point at the end of valid data. */
980					*off = m->m_len;
981					return (m);
982				}
983				return (NULL);
984			}
985			m = m->m_next;
986		}
987	}
988	return (NULL);
989}
990
991void
992m_print(const struct mbuf *m)
993{
994	int len;
995	const struct mbuf *m2;
996
997	len = m->m_pkthdr.len;
998	m2 = m;
999	while (len) {
1000		printf("%p %*D\n", m2, m2->m_len, (u_char *)m2->m_data, "-");
1001		len -= m2->m_len;
1002		m2 = m2->m_next;
1003	}
1004	return;
1005}
1006
1007u_int
1008m_fixhdr(struct mbuf *m0)
1009{
1010	u_int len;
1011
1012	len = m_length(m0, NULL);
1013	m0->m_pkthdr.len = len;
1014	return (len);
1015}
1016
1017u_int
1018m_length(struct mbuf *m0, struct mbuf **last)
1019{
1020	struct mbuf *m;
1021	u_int len;
1022
1023	len = 0;
1024	for (m = m0; m != NULL; m = m->m_next) {
1025		len += m->m_len;
1026		if (m->m_next == NULL)
1027			break;
1028	}
1029	if (last != NULL)
1030		*last = m;
1031	return (len);
1032}
1033
1034/*
1035 * Defragment a mbuf chain, returning the shortest possible
1036 * chain of mbufs and clusters.  If allocation fails and
1037 * this cannot be completed, NULL will be returned, but
1038 * the passed in chain will be unchanged.  Upon success,
1039 * the original chain will be freed, and the new chain
1040 * will be returned.
1041 *
1042 * If a non-packet header is passed in, the original
1043 * mbuf (chain?) will be returned unharmed.
1044 */
1045struct mbuf *
1046m_defrag(struct mbuf *m0, int how)
1047{
1048	struct mbuf *m_new = NULL, *m_final = NULL;
1049	int progress = 0, length;
1050
1051	if (!(m0->m_flags & M_PKTHDR))
1052		return (m0);
1053
1054	m_fixhdr(m0); /* Needed sanity check */
1055
1056#ifdef MBUF_STRESS_TEST
1057	if (m_defragrandomfailures) {
1058		int temp = arc4random() & 0xff;
1059		if (temp == 0xba)
1060			goto nospace;
1061	}
1062#endif
1063
1064	if (m0->m_pkthdr.len > MHLEN)
1065		m_final = m_getcl(how, MT_DATA, M_PKTHDR);
1066	else
1067		m_final = m_gethdr(how, MT_DATA);
1068
1069	if (m_final == NULL)
1070		goto nospace;
1071
1072	if (m_dup_pkthdr(m_final, m0, how) == 0)
1073		goto nospace;
1074
1075	m_new = m_final;
1076
1077	while (progress < m0->m_pkthdr.len) {
1078		length = m0->m_pkthdr.len - progress;
1079		if (length > MCLBYTES)
1080			length = MCLBYTES;
1081
1082		if (m_new == NULL) {
1083			if (length > MLEN)
1084				m_new = m_getcl(how, MT_DATA, 0);
1085			else
1086				m_new = m_get(how, MT_DATA);
1087			if (m_new == NULL)
1088				goto nospace;
1089		}
1090
1091		m_copydata(m0, progress, length, mtod(m_new, caddr_t));
1092		progress += length;
1093		m_new->m_len = length;
1094		if (m_new != m_final)
1095			m_cat(m_final, m_new);
1096		m_new = NULL;
1097	}
1098#ifdef MBUF_STRESS_TEST
1099	if (m0->m_next == NULL)
1100		m_defraguseless++;
1101#endif
1102	m_freem(m0);
1103	m0 = m_final;
1104#ifdef MBUF_STRESS_TEST
1105	m_defragpackets++;
1106	m_defragbytes += m0->m_pkthdr.len;
1107#endif
1108	return (m0);
1109nospace:
1110#ifdef MBUF_STRESS_TEST
1111	m_defragfailure++;
1112#endif
1113	if (m_new)
1114		m_free(m_new);
1115	if (m_final)
1116		m_freem(m_final);
1117	return (NULL);
1118}
1119
1120#ifdef MBUF_STRESS_TEST
1121
1122/*
1123 * Fragment an mbuf chain.  There's no reason you'd ever want to do
1124 * this in normal usage, but it's great for stress testing various
1125 * mbuf consumers.
1126 *
1127 * If fragmentation is not possible, the original chain will be
1128 * returned.
1129 *
1130 * Possible length values:
1131 * 0	 no fragmentation will occur
1132 * > 0	each fragment will be of the specified length
1133 * -1	each fragment will be the same random value in length
1134 * -2	each fragment's length will be entirely random
1135 * (Random values range from 1 to 256)
1136 */
1137struct mbuf *
1138m_fragment(struct mbuf *m0, int how, int length)
1139{
1140	struct mbuf *m_new = NULL, *m_final = NULL;
1141	int progress = 0;
1142
1143	if (!(m0->m_flags & M_PKTHDR))
1144		return (m0);
1145
1146	if ((length == 0) || (length < -2))
1147		return (m0);
1148
1149	m_fixhdr(m0); /* Needed sanity check */
1150
1151	m_final = m_getcl(how, MT_DATA, M_PKTHDR);
1152
1153	if (m_final == NULL)
1154		goto nospace;
1155
1156	if (m_dup_pkthdr(m_final, m0, how) == 0)
1157		goto nospace;
1158
1159	m_new = m_final;
1160
1161	if (length == -1)
1162		length = 1 + (arc4random() & 255);
1163
1164	while (progress < m0->m_pkthdr.len) {
1165		int fraglen;
1166
1167		if (length > 0)
1168			fraglen = length;
1169		else
1170			fraglen = 1 + (arc4random() & 255);
1171		if (fraglen > m0->m_pkthdr.len - progress)
1172			fraglen = m0->m_pkthdr.len - progress;
1173
1174		if (fraglen > MCLBYTES)
1175			fraglen = MCLBYTES;
1176
1177		if (m_new == NULL) {
1178			m_new = m_getcl(how, MT_DATA, 0);
1179			if (m_new == NULL)
1180				goto nospace;
1181		}
1182
1183		m_copydata(m0, progress, fraglen, mtod(m_new, caddr_t));
1184		progress += fraglen;
1185		m_new->m_len = fraglen;
1186		if (m_new != m_final)
1187			m_cat(m_final, m_new);
1188		m_new = NULL;
1189	}
1190	m_freem(m0);
1191	m0 = m_final;
1192	return (m0);
1193nospace:
1194	if (m_new)
1195		m_free(m_new);
1196	if (m_final)
1197		m_freem(m_final);
1198	/* Return the original chain on failure */
1199	return (m0);
1200}
1201
1202#endif
1203
1204struct mbuf *
1205m_uiotombuf(struct uio *uio, int how, int len)
1206{
1207	struct mbuf *m_new = NULL, *m_final = NULL;
1208	int progress = 0, error = 0, length, total;
1209
1210	if (len > 0)
1211		total = min(uio->uio_resid, len);
1212	else
1213		total = uio->uio_resid;
1214	if (total > MHLEN)
1215		m_final = m_getcl(how, MT_DATA, M_PKTHDR);
1216	else
1217		m_final = m_gethdr(how, MT_DATA);
1218	if (m_final == NULL)
1219		goto nospace;
1220	m_new = m_final;
1221	while (progress < total) {
1222		length = total - progress;
1223		if (length > MCLBYTES)
1224			length = MCLBYTES;
1225		if (m_new == NULL) {
1226			if (length > MLEN)
1227				m_new = m_getcl(how, MT_DATA, 0);
1228			else
1229				m_new = m_get(how, MT_DATA);
1230			if (m_new == NULL)
1231				goto nospace;
1232		}
1233		error = uiomove(mtod(m_new, void *), length, uio);
1234		if (error)
1235			goto nospace;
1236		progress += length;
1237		m_new->m_len = length;
1238		if (m_new != m_final)
1239			m_cat(m_final, m_new);
1240		m_new = NULL;
1241	}
1242	m_fixhdr(m_final);
1243	return (m_final);
1244nospace:
1245	if (m_new)
1246		m_free(m_new);
1247	if (m_final)
1248		m_freem(m_final);
1249	return (NULL);
1250}
1251