Revision 72853e2991a2702ae93aaf889ac7db743a415dd3 authored by Mel Gorman on 09 September 2010, 23:38:16 UTC, committed by Linus Torvalds on 10 September 2010, 01:57:25 UTC
When allocating a page, the system uses NR_FREE_PAGES counters to determine if watermarks would remain intact after the allocation was made. This check is made without interrupts disabled or the zone lock held and so is race-prone by nature. Unfortunately, when pages are being freed in batch, the counters are updated before the pages are added on the list. During this window, the counters are misleading as the pages do not exist yet. When under significant pressure on systems with large numbers of CPUs, it's possible for processes to make progress even though they should have been stalled. This is particularly problematic if a number of the processes are using GFP_ATOMIC as the min watermark can be accidentally breached and in extreme cases, the system can livelock. This patch updates the counters after the pages have been added to the list. This makes the allocator more cautious with respect to preserving the watermarks and mitigates livelock possibilities. [akpm@linux-foundation.org: avoid modifying incoming args] Signed-off-by: Mel Gorman <mel@csn.ul.ie> Reviewed-by: Rik van Riel <riel@redhat.com> Reviewed-by: Minchan Kim <minchan.kim@gmail.com> Reviewed-by: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com> Reviewed-by: Christoph Lameter <cl@linux.com> Reviewed-by: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com> Acked-by: Johannes Weiner <hannes@cmpxchg.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
1 parent 5ee28a4
lzo1x_compress.c
/*
* LZO1X Compressor from MiniLZO
*
* Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
*
* The full LZO package can be found at:
* http://www.oberhumer.com/opensource/lzo/
*
* Changed for kernel use by:
* Nitin Gupta <nitingupta910@gmail.com>
* Richard Purdie <rpurdie@openedhand.com>
*/
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/lzo.h>
#include <asm/unaligned.h>
#include "lzodefs.h"
static noinline size_t
_lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
unsigned char *out, size_t *out_len, void *wrkmem)
{
const unsigned char * const in_end = in + in_len;
const unsigned char * const ip_end = in + in_len - M2_MAX_LEN - 5;
const unsigned char ** const dict = wrkmem;
const unsigned char *ip = in, *ii = ip;
const unsigned char *end, *m, *m_pos;
size_t m_off, m_len, dindex;
unsigned char *op = out;
ip += 4;
for (;;) {
dindex = ((size_t)(0x21 * DX3(ip, 5, 5, 6)) >> 5) & D_MASK;
m_pos = dict[dindex];
if (m_pos < in)
goto literal;
if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
goto literal;
m_off = ip - m_pos;
if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
goto try_match;
dindex = (dindex & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f);
m_pos = dict[dindex];
if (m_pos < in)
goto literal;
if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
goto literal;
m_off = ip - m_pos;
if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
goto try_match;
goto literal;
try_match:
if (get_unaligned((const unsigned short *)m_pos)
== get_unaligned((const unsigned short *)ip)) {
if (likely(m_pos[2] == ip[2]))
goto match;
}
literal:
dict[dindex] = ip;
++ip;
if (unlikely(ip >= ip_end))
break;
continue;
match:
dict[dindex] = ip;
if (ip != ii) {
size_t t = ip - ii;
if (t <= 3) {
op[-2] |= t;
} else if (t <= 18) {
*op++ = (t - 3);
} else {
size_t tt = t - 18;
*op++ = 0;
while (tt > 255) {
tt -= 255;
*op++ = 0;
}
*op++ = tt;
}
do {
*op++ = *ii++;
} while (--t > 0);
}
ip += 3;
if (m_pos[3] != *ip++ || m_pos[4] != *ip++
|| m_pos[5] != *ip++ || m_pos[6] != *ip++
|| m_pos[7] != *ip++ || m_pos[8] != *ip++) {
--ip;
m_len = ip - ii;
if (m_off <= M2_MAX_OFFSET) {
m_off -= 1;
*op++ = (((m_len - 1) << 5)
| ((m_off & 7) << 2));
*op++ = (m_off >> 3);
} else if (m_off <= M3_MAX_OFFSET) {
m_off -= 1;
*op++ = (M3_MARKER | (m_len - 2));
goto m3_m4_offset;
} else {
m_off -= 0x4000;
*op++ = (M4_MARKER | ((m_off & 0x4000) >> 11)
| (m_len - 2));
goto m3_m4_offset;
}
} else {
end = in_end;
m = m_pos + M2_MAX_LEN + 1;
while (ip < end && *m == *ip) {
m++;
ip++;
}
m_len = ip - ii;
if (m_off <= M3_MAX_OFFSET) {
m_off -= 1;
if (m_len <= 33) {
*op++ = (M3_MARKER | (m_len - 2));
} else {
m_len -= 33;
*op++ = M3_MARKER | 0;
goto m3_m4_len;
}
} else {
m_off -= 0x4000;
if (m_len <= M4_MAX_LEN) {
*op++ = (M4_MARKER
| ((m_off & 0x4000) >> 11)
| (m_len - 2));
} else {
m_len -= M4_MAX_LEN;
*op++ = (M4_MARKER
| ((m_off & 0x4000) >> 11));
m3_m4_len:
while (m_len > 255) {
m_len -= 255;
*op++ = 0;
}
*op++ = (m_len);
}
}
m3_m4_offset:
*op++ = ((m_off & 63) << 2);
*op++ = (m_off >> 6);
}
ii = ip;
if (unlikely(ip >= ip_end))
break;
}
*out_len = op - out;
return in_end - ii;
}
int lzo1x_1_compress(const unsigned char *in, size_t in_len, unsigned char *out,
size_t *out_len, void *wrkmem)
{
const unsigned char *ii;
unsigned char *op = out;
size_t t;
if (unlikely(in_len <= M2_MAX_LEN + 5)) {
t = in_len;
} else {
t = _lzo1x_1_do_compress(in, in_len, op, out_len, wrkmem);
op += *out_len;
}
if (t > 0) {
ii = in + in_len - t;
if (op == out && t <= 238) {
*op++ = (17 + t);
} else if (t <= 3) {
op[-2] |= t;
} else if (t <= 18) {
*op++ = (t - 3);
} else {
size_t tt = t - 18;
*op++ = 0;
while (tt > 255) {
tt -= 255;
*op++ = 0;
}
*op++ = tt;
}
do {
*op++ = *ii++;
} while (--t > 0);
}
*op++ = M4_MARKER | 1;
*op++ = 0;
*op++ = 0;
*out_len = op - out;
return LZO_E_OK;
}
EXPORT_SYMBOL_GPL(lzo1x_1_compress);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("LZO1X-1 Compressor");
Computing file changes ...
