Attachment #22330 for bug #38777

View | Details | Raw Unified | Return to bug 38777
Collapse All | Expand All

Lines 76-82 Link Here

(-)articles/committers-guide/article.sgml (-2 / +2 lines)
76		76
77	<row>	77	<row>
78	<entry><emphasis>Noteworthy CVS Tags</emphasis></entry>	78	<entry><emphasis>Noteworthy CVS Tags</emphasis></entry>
79	<entry><literal>RELENG_4</literal> (4.x-STABLE), <literal>HEAD</literal> (-CURRENT)</entry>	79	<entry><literal>RELENG_4</literal> (4.X-STABLE), <literal>HEAD</literal> (-CURRENT)</entry>
80	</row>	80	</row>
81	</tbody>	81	</tbody>
82	</tgroup>	82	</tgroup>
Lines 323-329 Link Here
323		323
324	<listitem>	324	<listitem>
325	<para>Check out the <filename>miscfs</filename> module as	325	<para>Check out the <filename>miscfs</filename> module as
326	it is in the 4.x branch:</para>	326	it is in the 4.X branch:</para>
327		327
328	<screen>&prompt.user; <userinput>cvs co -rRELENG_4 miscfs</userinput></screen>	328	<screen>&prompt.user; <userinput>cvs co -rRELENG_4 miscfs</userinput></screen>
329		329

Lines 118-124 Link Here

(-)articles/java-tomcat/article.sgml (-1 / +1 lines)
118		118
119	<para>The Tomcat portion of the install is very straight forward, but	119	<para>The Tomcat portion of the install is very straight forward, but
120	the difficulty I had was getting Java Development Kit up and	120	the difficulty I had was getting Java Development Kit up and
121	running for FreeBSD 4.x, as Sun Microsystems only supplies	121	running for FreeBSD 4.X, as Sun Microsystems only supplies
122	Binaries for Linux, Solaris, and Windows NT. This means that I	122	Binaries for Linux, Solaris, and Windows NT. This means that I
123	had to compile my own JDK for FreeBSD. I began by searching for	123	had to compile my own JDK for FreeBSD. I began by searching for
124	documentation on the Internet. I quickly found that there is more	124	documentation on the Internet. I quickly found that there is more

Lines 8-14 Link Here

(-)articles/releng/branches.ascii (-2 / +2 lines)
8	\| RELENG_3	8	\| RELENG_3
9	H ______\|____ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ + - - - - - - +	9	H ______\|____ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ + - - - - - - +
10	E / \ \| \| \| \| \| \| \| \| \| \| \| \|	10	E / \ \| \| \| \| \| \| \| \| \| \| \| \|
11	A \|3.1-RELEASE\|-\|3.2R \|-\|3.3R \|-\|3.4R \|-\|3.5R \|-\| 3.5.1R\|---\| 3.x-STABLE \|	11	A \|3.1-RELEASE\|-\|3.2R \|-\|3.3R \|-\|3.4R \|-\|3.5R \|-\| 3.5.1R\|---\| 3.X-STABLE \|
12	D \___________/ \|_ _ _\| \|_ _ _\| \|_ _ _\| \|_ _ _\| \|_ _ _ _\| \| \|	12	D \___________/ \|_ _ _\| \|_ _ _\| \|_ _ _\| \|_ _ _\| \|_ _ _ _\| \| \|
13	\| + - - - - - - +	13	\| + - - - - - - +
14	\|	14	\|
Lines 19-25 Link Here
19	\| RELENG_4	19	\| RELENG_4
20	_____\|_____ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ + - - - - - - +	20	_____\|_____ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ + - - - - - - +
21	/ \ \| \| \| \| \| \| \| \| \| \| \| \|	21	/ \ \| \| \| \| \| \| \| \| \| \| \| \|
22	\|4.0-RELEASE\|-\|4.1R \|-\|4.1.1R \|-\|4.2R \|-\|4.3R \|-\|4.4R \|---\| 4.x-STABLE \|	22	\|4.0-RELEASE\|-\|4.1R \|-\|4.1.1R \|-\|4.2R \|-\|4.3R \|-\|4.4R \|---\| 4.X-STABLE \|
23	\___________/ \|_ _ _\| \|_ _ _ _\| \|_ _ _\| \|_ _ _\| \|_ _ _\| \| \|	23	\___________/ \|_ _ _\| \|_ _ _ _\| \|_ _ _\| \|_ _ _\| \|_ _ _\| \| \|
24	\| ___\| \|__ + - - - - - - +	24	\| ___\| \|__ + - - - - - - +
25	\| _ _ _ \| _ _ _ _ _ \|_ _ _ __	25	\| _ _ _ \| _ _ _ _ _ \|_ _ _ __




      However, the swap management structure has had problems
      historically.</para>

    <para>Under FreeBSD 3.X the swap management structure preallocates an
      array that encompasses the entire object requiring swap backing
      store&mdash;even if only a few pages of that object are swap-backed.
      This creates a kernel memory fragmentation problem when large objects

      fly for additional swap management structures when a swapout occurs.  It
      is evident that there was plenty of room for improvement.</para>

    <para>For FreeBSD 4.X, I completely rewrote the swap subsystem.  With this
      rewrite, swap management structures are allocated through a hash table
      rather than a linear array giving them a fixed allocation size and much
      finer granularity.  Rather then using a linearly linked list to keep

      <qandaentry>
	<question>
	  <para>What is <quote>the interleaving algorithm</quote> that you
	    refer to in your listing of the ills of the FreeBSD 3.X swap
	    arrangements?</para>
	</question>



	  <literallayout>A B C D A B C D A B C D A B C D</literallayout>

	  <para>FreeBSD 3.X uses a <quote>sequential list of free
	    regions</quote> approach to accounting for the free swap areas.
	    The idea is that large blocks of free linear space can be
	    represented with a single list node

	    it is to try to put that sophistication elsewhere.</para>

	  <para>The fragmentation causes other problems.  Being a linear list
	    under 3.X, and having such a huge amount of inherent
	    fragmentation, allocating and freeing swap winds up being an O(N)
	    algorithm instead of an O(1) algorithm.  Combined with other
	    factors (heavy swapping) and you start getting into O(N^2) and
	    O(N^3) levels of overhead, which is bad.  The 3.X system may also
	    need to allocate KVM during a swap operation to create a new list
	    node which can lead to a deadlock if the system is trying to
	    pageout pages in a low-memory situation.</para>

	  <para>Under 4.X we do not use a sequential list.  Instead we use a
	    radix tree and bitmaps of swap blocks rather than ranged list
	    nodes.  We take the hit of preallocating all the bitmaps required
	    for the entire swap area up front but it winds up wasting less

Return to bug 38777

Lines 312-318 Link Here

(-)articles/vm-design/article.sgml (-7 / +7 lines)
312	However, the swap management structure has had problems	312	However, the swap management structure has had problems
313	historically.</para>	313	historically.</para>
314		314
315	<para>Under FreeBSD 3.x the swap management structure preallocates an	315	<para>Under FreeBSD 3.X the swap management structure preallocates an
316	array that encompasses the entire object requiring swap backing	316	array that encompasses the entire object requiring swap backing
317	store—even if only a few pages of that object are swap-backed.	317	store—even if only a few pages of that object are swap-backed.
318	This creates a kernel memory fragmentation problem when large objects	318	This creates a kernel memory fragmentation problem when large objects
Lines 329-335 Link Here
329	fly for additional swap management structures when a swapout occurs. It	329	fly for additional swap management structures when a swapout occurs. It
330	is evident that there was plenty of room for improvement.</para>	330	is evident that there was plenty of room for improvement.</para>
331		331
332	<para>For FreeBSD 4.x, I completely rewrote the swap subsystem. With this	332	<para>For FreeBSD 4.X, I completely rewrote the swap subsystem. With this
333	rewrite, swap management structures are allocated through a hash table	333	rewrite, swap management structures are allocated through a hash table
334	rather than a linear array giving them a fixed allocation size and much	334	rather than a linear array giving them a fixed allocation size and much
335	finer granularity. Rather then using a linearly linked list to keep	335	finer granularity. Rather then using a linearly linked list to keep
Lines 558-564 Link Here
558	<qandaentry>	558	<qandaentry>
559	<question>	559	<question>
560	<para>What is <quote>the interleaving algorithm</quote> that you	560	<para>What is <quote>the interleaving algorithm</quote> that you
561	refer to in your listing of the ills of the FreeBSD 3.x swap	561	refer to in your listing of the ills of the FreeBSD 3.X swap
562	arrangements?</para>	562	arrangements?</para>
563	</question>	563	</question>
564		564
Lines 574-580 Link Here
574		574
575	<literallayout>A B C D A B C D A B C D A B C D</literallayout>	575	<literallayout>A B C D A B C D A B C D A B C D</literallayout>
576		576
577	<para>FreeBSD 3.x uses a <quote>sequential list of free	577	<para>FreeBSD 3.X uses a <quote>sequential list of free
578	regions</quote> approach to accounting for the free swap areas.	578	regions</quote> approach to accounting for the free swap areas.
579	The idea is that large blocks of free linear space can be	579	The idea is that large blocks of free linear space can be
580	represented with a single list node	580	represented with a single list node
Lines 593-608 Link Here
593	it is to try to put that sophistication elsewhere.</para>	593	it is to try to put that sophistication elsewhere.</para>
594		594
595	<para>The fragmentation causes other problems. Being a linear list	595	<para>The fragmentation causes other problems. Being a linear list
596	under 3.x, and having such a huge amount of inherent	596	under 3.X, and having such a huge amount of inherent
597	fragmentation, allocating and freeing swap winds up being an O(N)	597	fragmentation, allocating and freeing swap winds up being an O(N)
598	algorithm instead of an O(1) algorithm. Combined with other	598	algorithm instead of an O(1) algorithm. Combined with other
599	factors (heavy swapping) and you start getting into O(N^2) and	599	factors (heavy swapping) and you start getting into O(N^2) and
600	O(N^3) levels of overhead, which is bad. The 3.x system may also	600	O(N^3) levels of overhead, which is bad. The 3.X system may also
601	need to allocate KVM during a swap operation to create a new list	601	need to allocate KVM during a swap operation to create a new list
602	node which can lead to a deadlock if the system is trying to	602	node which can lead to a deadlock if the system is trying to
603	pageout pages in a low-memory situation.</para>	603	pageout pages in a low-memory situation.</para>
604		604
605	<para>Under 4.x we do not use a sequential list. Instead we use a	605	<para>Under 4.X we do not use a sequential list. Instead we use a
606	radix tree and bitmaps of swap blocks rather than ranged list	606	radix tree and bitmaps of swap blocks rather than ranged list
607	nodes. We take the hit of preallocating all the bitmaps required	607	nodes. We take the hit of preallocating all the bitmaps required
608	for the entire swap area up front but it winds up wasting less	608	for the entire swap area up front but it winds up wasting less