debuggers.hg

annotate xen/common/lzo.c @ 22855:1d1eec7e1fb4

xl: Perform minimal validation of virtual disk file while parsing config file

This patch performs some very basic validation on the virtual disk
file passed through the config file. This validation ensures that we
don't go too far with the initialization like spawn qemu and more
while there could be some potentially fundamental issues.

[ Patch fixed up to work with PHYSTYPE_EMPTY 22808:6ec61438713a -iwj ]

Signed-off-by: Kamala Narasimhan <kamala.narasimhan@citrix.com>
Acked-by: Ian Jackson <ian.jackson@eu.citrix.com>
Signed-off-by: Ian Jackson <ian.jackson@eu.citrix.com>
Committed-by: Ian Jackson <ian.jackson@eu.citrix.com>
author Kamala Narasimhan <kamala.narasimhan@gmail.com>
date Tue Jan 25 18:09:49 2011 +0000 (2011-01-25)
parents f210a633571c
children
rev   line source
keir@19684 1 /*
keir@19684 2 * lzo.c -- LZO1X Compressor from MiniLZO
keir@19684 3 *
keir@19684 4 * Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
keir@19684 5 *
keir@19684 6 * The full LZO package can be found at:
keir@19684 7 * http://www.oberhumer.com/opensource/lzo/
keir@19684 8 *
keir@19684 9 * Adapted for Xen (files combined and syntactic/header changes) by:
keir@19684 10 * Dan Magenheimer <dan.magenheimer@oracle.com>
keir@19684 11 *
keir@19684 12 */
keir@19684 13
keir@19684 14 /*
keir@19684 15 * lzodefs.h -- architecture, OS and compiler specific defines
keir@19684 16 *
keir@19684 17 * Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
keir@19684 18 *
keir@19684 19 * The full LZO package can be found at:
keir@19684 20 * http://www.oberhumer.com/opensource/lzo/
keir@19684 21 *
keir@19684 22 * Changed for kernel use by:
keir@19684 23 * Nitin Gupta <nitingupta910@gmail.com>
keir@19684 24 * Richard Purdie <rpurdie@openedhand.com>
keir@19684 25 */
keir@19684 26
keir@19684 27 #define LZO_VERSION 0x2020
keir@19684 28 #define LZO_VERSION_STRING "2.02"
keir@19684 29 #define LZO_VERSION_DATE "Oct 17 2005"
keir@19684 30
keir@19684 31 #define M1_MAX_OFFSET 0x0400
keir@19684 32 #define M2_MAX_OFFSET 0x0800
keir@19684 33 #define M3_MAX_OFFSET 0x4000
keir@19684 34 #define M4_MAX_OFFSET 0xbfff
keir@19684 35
keir@19684 36 #define M1_MIN_LEN 2
keir@19684 37 #define M1_MAX_LEN 2
keir@19684 38 #define M2_MIN_LEN 3
keir@19684 39 #define M2_MAX_LEN 8
keir@19684 40 #define M3_MIN_LEN 3
keir@19684 41 #define M3_MAX_LEN 33
keir@19684 42 #define M4_MIN_LEN 3
keir@19684 43 #define M4_MAX_LEN 9
keir@19684 44
keir@19684 45 #define M1_MARKER 0
keir@19684 46 #define M2_MARKER 64
keir@19684 47 #define M3_MARKER 32
keir@19684 48 #define M4_MARKER 16
keir@19684 49
keir@19684 50 #define D_BITS 14
keir@19684 51 #define D_MASK ((1u << D_BITS) - 1)
keir@19684 52 #define D_HIGH ((D_MASK >> 1) + 1)
keir@19684 53
keir@19684 54 #define DX2(p, s1, s2) (((((size_t)((p)[2]) << (s2)) ^ (p)[1]) \
keir@19684 55 << (s1)) ^ (p)[0])
keir@19684 56 #define DX3(p, s1, s2, s3) ((DX2((p)+1, s2, s3) << (s1)) ^ (p)[0])
keir@19684 57
keir@19684 58 /*
keir@19684 59 * LZO1X Compressor from MiniLZO
keir@19684 60 *
keir@19684 61 * Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
keir@19684 62 *
keir@19684 63 * The full LZO package can be found at:
keir@19684 64 * http://www.oberhumer.com/opensource/lzo/
keir@19684 65 *
keir@19684 66 * Changed for kernel use by:
keir@19684 67 * Nitin Gupta <nitingupta910@gmail.com>
keir@19684 68 * Richard Purdie <rpurdie@openedhand.com>
keir@19684 69 */
keir@19684 70
keir@19684 71 #include <xen/types.h>
keir@19684 72 #include <xen/lzo.h>
keir@19684 73 #define get_unaligned(_p) (*(_p))
keir@19684 74 #define put_unaligned(_val,_p) (*(_p)=_val)
keir@19684 75 #define get_unaligned_le16(_p) (*(u16 *)(_p))
keir@19684 76
keir@19684 77 static noinline size_t
keir@19684 78 _lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
keir@19684 79 unsigned char *out, size_t *out_len, void *wrkmem)
keir@19684 80 {
keir@19684 81 const unsigned char * const in_end = in + in_len;
keir@19684 82 const unsigned char * const ip_end = in + in_len - M2_MAX_LEN - 5;
keir@19684 83 const unsigned char ** const dict = wrkmem;
keir@19684 84 const unsigned char *ip = in, *ii = ip;
keir@19684 85 const unsigned char *end, *m, *m_pos;
keir@19684 86 size_t m_off, m_len, dindex;
keir@19684 87 unsigned char *op = out;
keir@19684 88
keir@19684 89 ip += 4;
keir@19684 90
keir@19684 91 for (;;) {
keir@19684 92 dindex = ((size_t)(0x21 * DX3(ip, 5, 5, 6)) >> 5) & D_MASK;
keir@19684 93 m_pos = dict[dindex];
keir@19684 94
keir@19684 95 if (m_pos < in)
keir@19684 96 goto literal;
keir@19684 97
keir@19684 98 if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
keir@19684 99 goto literal;
keir@19684 100
keir@19684 101 m_off = ip - m_pos;
keir@19684 102 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
keir@19684 103 goto try_match;
keir@19684 104
keir@19684 105 dindex = (dindex & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f);
keir@19684 106 m_pos = dict[dindex];
keir@19684 107
keir@19684 108 if (m_pos < in)
keir@19684 109 goto literal;
keir@19684 110
keir@19684 111 if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
keir@19684 112 goto literal;
keir@19684 113
keir@19684 114 m_off = ip - m_pos;
keir@19684 115 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
keir@19684 116 goto try_match;
keir@19684 117
keir@19684 118 goto literal;
keir@19684 119
keir@19684 120 try_match:
keir@19684 121 if (get_unaligned((const unsigned short *)m_pos)
keir@19684 122 == get_unaligned((const unsigned short *)ip)) {
keir@19684 123 if (likely(m_pos[2] == ip[2]))
keir@19684 124 goto match;
keir@19684 125 }
keir@19684 126
keir@19684 127 literal:
keir@19684 128 dict[dindex] = ip;
keir@19684 129 ++ip;
keir@19684 130 if (unlikely(ip >= ip_end))
keir@19684 131 break;
keir@19684 132 continue;
keir@19684 133
keir@19684 134 match:
keir@19684 135 dict[dindex] = ip;
keir@19684 136 if (ip != ii) {
keir@19684 137 size_t t = ip - ii;
keir@19684 138
keir@19684 139 if (t <= 3) {
keir@19684 140 op[-2] |= t;
keir@19684 141 } else if (t <= 18) {
keir@19684 142 *op++ = (t - 3);
keir@19684 143 } else {
keir@19684 144 size_t tt = t - 18;
keir@19684 145
keir@19684 146 *op++ = 0;
keir@19684 147 while (tt > 255) {
keir@19684 148 tt -= 255;
keir@19684 149 *op++ = 0;
keir@19684 150 }
keir@19684 151 *op++ = tt;
keir@19684 152 }
keir@19684 153 do {
keir@19684 154 *op++ = *ii++;
keir@19684 155 } while (--t > 0);
keir@19684 156 }
keir@19684 157
keir@19684 158 ip += 3;
keir@19684 159 if (m_pos[3] != *ip++ || m_pos[4] != *ip++
keir@19684 160 || m_pos[5] != *ip++ || m_pos[6] != *ip++
keir@19684 161 || m_pos[7] != *ip++ || m_pos[8] != *ip++) {
keir@19684 162 --ip;
keir@19684 163 m_len = ip - ii;
keir@19684 164
keir@19684 165 if (m_off <= M2_MAX_OFFSET) {
keir@19684 166 m_off -= 1;
keir@19684 167 *op++ = (((m_len - 1) << 5)
keir@19684 168 | ((m_off & 7) << 2));
keir@19684 169 *op++ = (m_off >> 3);
keir@19684 170 } else if (m_off <= M3_MAX_OFFSET) {
keir@19684 171 m_off -= 1;
keir@19684 172 *op++ = (M3_MARKER | (m_len - 2));
keir@19684 173 goto m3_m4_offset;
keir@19684 174 } else {
keir@19684 175 m_off -= 0x4000;
keir@19684 176
keir@19684 177 *op++ = (M4_MARKER | ((m_off & 0x4000) >> 11)
keir@19684 178 | (m_len - 2));
keir@19684 179 goto m3_m4_offset;
keir@19684 180 }
keir@19684 181 } else {
keir@19684 182 end = in_end;
keir@19684 183 m = m_pos + M2_MAX_LEN + 1;
keir@19684 184
keir@19684 185 while (ip < end && *m == *ip) {
keir@19684 186 m++;
keir@19684 187 ip++;
keir@19684 188 }
keir@19684 189 m_len = ip - ii;
keir@19684 190
keir@19684 191 if (m_off <= M3_MAX_OFFSET) {
keir@19684 192 m_off -= 1;
keir@19684 193 if (m_len <= 33) {
keir@19684 194 *op++ = (M3_MARKER | (m_len - 2));
keir@19684 195 } else {
keir@19684 196 m_len -= 33;
keir@19684 197 *op++ = M3_MARKER | 0;
keir@19684 198 goto m3_m4_len;
keir@19684 199 }
keir@19684 200 } else {
keir@19684 201 m_off -= 0x4000;
keir@19684 202 if (m_len <= M4_MAX_LEN) {
keir@19684 203 *op++ = (M4_MARKER
keir@19684 204 | ((m_off & 0x4000) >> 11)
keir@19684 205 | (m_len - 2));
keir@19684 206 } else {
keir@19684 207 m_len -= M4_MAX_LEN;
keir@19684 208 *op++ = (M4_MARKER
keir@19684 209 | ((m_off & 0x4000) >> 11));
keir@19684 210 m3_m4_len:
keir@19684 211 while (m_len > 255) {
keir@19684 212 m_len -= 255;
keir@19684 213 *op++ = 0;
keir@19684 214 }
keir@19684 215
keir@19684 216 *op++ = (m_len);
keir@19684 217 }
keir@19684 218 }
keir@19684 219 m3_m4_offset:
keir@19684 220 *op++ = ((m_off & 63) << 2);
keir@19684 221 *op++ = (m_off >> 6);
keir@19684 222 }
keir@19684 223
keir@19684 224 ii = ip;
keir@19684 225 if (unlikely(ip >= ip_end))
keir@19684 226 break;
keir@19684 227 }
keir@19684 228
keir@19684 229 *out_len = op - out;
keir@19684 230 return in_end - ii;
keir@19684 231 }
keir@19684 232
keir@19684 233 int lzo1x_1_compress(const unsigned char *in, size_t in_len, unsigned char *out,
keir@19684 234 size_t *out_len, void *wrkmem)
keir@19684 235 {
keir@19684 236 const unsigned char *ii;
keir@19684 237 unsigned char *op = out;
keir@19684 238 size_t t;
keir@19684 239
keir@19684 240 if (unlikely(in_len <= M2_MAX_LEN + 5)) {
keir@19684 241 t = in_len;
keir@19684 242 } else {
keir@19684 243 t = _lzo1x_1_do_compress(in, in_len, op, out_len, wrkmem);
keir@19684 244 op += *out_len;
keir@19684 245 }
keir@19684 246
keir@19684 247 if (t > 0) {
keir@19684 248 ii = in + in_len - t;
keir@19684 249
keir@19684 250 if (op == out && t <= 238) {
keir@19684 251 *op++ = (17 + t);
keir@19684 252 } else if (t <= 3) {
keir@19684 253 op[-2] |= t;
keir@19684 254 } else if (t <= 18) {
keir@19684 255 *op++ = (t - 3);
keir@19684 256 } else {
keir@19684 257 size_t tt = t - 18;
keir@19684 258
keir@19684 259 *op++ = 0;
keir@19684 260 while (tt > 255) {
keir@19684 261 tt -= 255;
keir@19684 262 *op++ = 0;
keir@19684 263 }
keir@19684 264
keir@19684 265 *op++ = tt;
keir@19684 266 }
keir@19684 267 do {
keir@19684 268 *op++ = *ii++;
keir@19684 269 } while (--t > 0);
keir@19684 270 }
keir@19684 271
keir@19684 272 *op++ = M4_MARKER | 1;
keir@19684 273 *op++ = 0;
keir@19684 274 *op++ = 0;
keir@19684 275
keir@19684 276 *out_len = op - out;
keir@19684 277 return LZO_E_OK;
keir@19684 278 }
keir@19684 279
keir@19684 280 /*
keir@19684 281 * LZO1X Decompressor from MiniLZO
keir@19684 282 *
keir@19684 283 * Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
keir@19684 284 *
keir@19684 285 * The full LZO package can be found at:
keir@19684 286 * http://www.oberhumer.com/opensource/lzo/
keir@19684 287 *
keir@19684 288 * Changed for kernel use by:
keir@19684 289 * Nitin Gupta <nitingupta910@gmail.com>
keir@19684 290 * Richard Purdie <rpurdie@openedhand.com>
keir@19684 291 */
keir@19684 292
keir@19684 293 #define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
keir@19684 294 #define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
keir@19684 295 #define HAVE_LB(m_pos, out, op) (m_pos < out || m_pos >= op)
keir@19684 296
keir@19684 297 #define COPY4(dst, src) \
keir@19684 298 put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
keir@19684 299
keir@19684 300 int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
keir@19684 301 unsigned char *out, size_t *out_len)
keir@19684 302 {
keir@19684 303 const unsigned char * const ip_end = in + in_len;
keir@19684 304 unsigned char * const op_end = out + *out_len;
keir@19684 305 const unsigned char *ip = in, *m_pos;
keir@19684 306 unsigned char *op = out;
keir@19684 307 size_t t;
keir@19684 308
keir@19684 309 *out_len = 0;
keir@19684 310
keir@19684 311 if (*ip > 17) {
keir@19684 312 t = *ip++ - 17;
keir@19684 313 if (t < 4)
keir@19684 314 goto match_next;
keir@19684 315 if (HAVE_OP(t, op_end, op))
keir@19684 316 goto output_overrun;
keir@19684 317 if (HAVE_IP(t + 1, ip_end, ip))
keir@19684 318 goto input_overrun;
keir@19684 319 do {
keir@19684 320 *op++ = *ip++;
keir@19684 321 } while (--t > 0);
keir@19684 322 goto first_literal_run;
keir@19684 323 }
keir@19684 324
keir@19684 325 while ((ip < ip_end)) {
keir@19684 326 t = *ip++;
keir@19684 327 if (t >= 16)
keir@19684 328 goto match;
keir@19684 329 if (t == 0) {
keir@19684 330 if (HAVE_IP(1, ip_end, ip))
keir@19684 331 goto input_overrun;
keir@19684 332 while (*ip == 0) {
keir@19684 333 t += 255;
keir@19684 334 ip++;
keir@19684 335 if (HAVE_IP(1, ip_end, ip))
keir@19684 336 goto input_overrun;
keir@19684 337 }
keir@19684 338 t += 15 + *ip++;
keir@19684 339 }
keir@19684 340 if (HAVE_OP(t + 3, op_end, op))
keir@19684 341 goto output_overrun;
keir@19684 342 if (HAVE_IP(t + 4, ip_end, ip))
keir@19684 343 goto input_overrun;
keir@19684 344
keir@19684 345 COPY4(op, ip);
keir@19684 346 op += 4;
keir@19684 347 ip += 4;
keir@19684 348 if (--t > 0) {
keir@19684 349 if (t >= 4) {
keir@19684 350 do {
keir@19684 351 COPY4(op, ip);
keir@19684 352 op += 4;
keir@19684 353 ip += 4;
keir@19684 354 t -= 4;
keir@19684 355 } while (t >= 4);
keir@19684 356 if (t > 0) {
keir@19684 357 do {
keir@19684 358 *op++ = *ip++;
keir@19684 359 } while (--t > 0);
keir@19684 360 }
keir@19684 361 } else {
keir@19684 362 do {
keir@19684 363 *op++ = *ip++;
keir@19684 364 } while (--t > 0);
keir@19684 365 }
keir@19684 366 }
keir@19684 367
keir@19684 368 first_literal_run:
keir@19684 369 t = *ip++;
keir@19684 370 if (t >= 16)
keir@19684 371 goto match;
keir@19684 372 m_pos = op - (1 + M2_MAX_OFFSET);
keir@19684 373 m_pos -= t >> 2;
keir@19684 374 m_pos -= *ip++ << 2;
keir@19684 375
keir@19684 376 if (HAVE_LB(m_pos, out, op))
keir@19684 377 goto lookbehind_overrun;
keir@19684 378
keir@19684 379 if (HAVE_OP(3, op_end, op))
keir@19684 380 goto output_overrun;
keir@19684 381 *op++ = *m_pos++;
keir@19684 382 *op++ = *m_pos++;
keir@19684 383 *op++ = *m_pos;
keir@19684 384
keir@19684 385 goto match_done;
keir@19684 386
keir@19684 387 do {
keir@19684 388 match:
keir@19684 389 if (t >= 64) {
keir@19684 390 m_pos = op - 1;
keir@19684 391 m_pos -= (t >> 2) & 7;
keir@19684 392 m_pos -= *ip++ << 3;
keir@19684 393 t = (t >> 5) - 1;
keir@19684 394 if (HAVE_LB(m_pos, out, op))
keir@19684 395 goto lookbehind_overrun;
keir@19684 396 if (HAVE_OP(t + 3 - 1, op_end, op))
keir@19684 397 goto output_overrun;
keir@19684 398 goto copy_match;
keir@19684 399 } else if (t >= 32) {
keir@19684 400 t &= 31;
keir@19684 401 if (t == 0) {
keir@19684 402 if (HAVE_IP(1, ip_end, ip))
keir@19684 403 goto input_overrun;
keir@19684 404 while (*ip == 0) {
keir@19684 405 t += 255;
keir@19684 406 ip++;
keir@19684 407 if (HAVE_IP(1, ip_end, ip))
keir@19684 408 goto input_overrun;
keir@19684 409 }
keir@19684 410 t += 31 + *ip++;
keir@19684 411 }
keir@19684 412 m_pos = op - 1;
keir@19684 413 m_pos -= get_unaligned_le16(ip) >> 2;
keir@19684 414 ip += 2;
keir@19684 415 } else if (t >= 16) {
keir@19684 416 m_pos = op;
keir@19684 417 m_pos -= (t & 8) << 11;
keir@19684 418
keir@19684 419 t &= 7;
keir@19684 420 if (t == 0) {
keir@19684 421 if (HAVE_IP(1, ip_end, ip))
keir@19684 422 goto input_overrun;
keir@19684 423 while (*ip == 0) {
keir@19684 424 t += 255;
keir@19684 425 ip++;
keir@19684 426 if (HAVE_IP(1, ip_end, ip))
keir@19684 427 goto input_overrun;
keir@19684 428 }
keir@19684 429 t += 7 + *ip++;
keir@19684 430 }
keir@19684 431 m_pos -= get_unaligned_le16(ip) >> 2;
keir@19684 432 ip += 2;
keir@19684 433 if (m_pos == op)
keir@19684 434 goto eof_found;
keir@19684 435 m_pos -= 0x4000;
keir@19684 436 } else {
keir@19684 437 m_pos = op - 1;
keir@19684 438 m_pos -= t >> 2;
keir@19684 439 m_pos -= *ip++ << 2;
keir@19684 440
keir@19684 441 if (HAVE_LB(m_pos, out, op))
keir@19684 442 goto lookbehind_overrun;
keir@19684 443 if (HAVE_OP(2, op_end, op))
keir@19684 444 goto output_overrun;
keir@19684 445
keir@19684 446 *op++ = *m_pos++;
keir@19684 447 *op++ = *m_pos;
keir@19684 448 goto match_done;
keir@19684 449 }
keir@19684 450
keir@19684 451 if (HAVE_LB(m_pos, out, op))
keir@19684 452 goto lookbehind_overrun;
keir@19684 453 if (HAVE_OP(t + 3 - 1, op_end, op))
keir@19684 454 goto output_overrun;
keir@19684 455
keir@19684 456 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
keir@19684 457 COPY4(op, m_pos);
keir@19684 458 op += 4;
keir@19684 459 m_pos += 4;
keir@19684 460 t -= 4 - (3 - 1);
keir@19684 461 do {
keir@19684 462 COPY4(op, m_pos);
keir@19684 463 op += 4;
keir@19684 464 m_pos += 4;
keir@19684 465 t -= 4;
keir@19684 466 } while (t >= 4);
keir@19684 467 if (t > 0)
keir@19684 468 do {
keir@19684 469 *op++ = *m_pos++;
keir@19684 470 } while (--t > 0);
keir@19684 471 } else {
keir@19684 472 copy_match:
keir@19684 473 *op++ = *m_pos++;
keir@19684 474 *op++ = *m_pos++;
keir@19684 475 do {
keir@19684 476 *op++ = *m_pos++;
keir@19684 477 } while (--t > 0);
keir@19684 478 }
keir@19684 479 match_done:
keir@19684 480 t = ip[-2] & 3;
keir@19684 481 if (t == 0)
keir@19684 482 break;
keir@19684 483 match_next:
keir@19684 484 if (HAVE_OP(t, op_end, op))
keir@19684 485 goto output_overrun;
keir@19684 486 if (HAVE_IP(t + 1, ip_end, ip))
keir@19684 487 goto input_overrun;
keir@19684 488
keir@19684 489 *op++ = *ip++;
keir@19684 490 if (t > 1) {
keir@19684 491 *op++ = *ip++;
keir@19684 492 if (t > 2)
keir@19684 493 *op++ = *ip++;
keir@19684 494 }
keir@19684 495
keir@19684 496 t = *ip++;
keir@19684 497 } while (ip < ip_end);
keir@19684 498 }
keir@19684 499
keir@19684 500 *out_len = op - out;
keir@19684 501 return LZO_E_EOF_NOT_FOUND;
keir@19684 502
keir@19684 503 eof_found:
keir@19684 504 *out_len = op - out;
keir@19684 505 return (ip == ip_end ? LZO_E_OK :
keir@19684 506 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
keir@19684 507 input_overrun:
keir@19684 508 *out_len = op - out;
keir@19684 509 return LZO_E_INPUT_OVERRUN;
keir@19684 510
keir@19684 511 output_overrun:
keir@19684 512 *out_len = op - out;
keir@19684 513 return LZO_E_OUTPUT_OVERRUN;
keir@19684 514
keir@19684 515 lookbehind_overrun:
keir@19684 516 *out_len = op - out;
keir@19684 517 return LZO_E_LOOKBEHIND_OVERRUN;
keir@19684 518 }