debuggers.hg

view xen/common/unlzma.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 0d7fb1ab92f4
children
line source
1 /* Lzma decompressor for Linux kernel. Shamelessly snarfed
2 * from busybox 1.1.1
3 *
4 * Linux kernel adaptation
5 * Copyright (C) 2006 Alain < alain@knaff.lu >
6 *
7 * Based on small lzma deflate implementation/Small range coder
8 * implementation for lzma.
9 * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >
10 *
11 * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
12 * Copyright (C) 1999-2005 Igor Pavlov
13 *
14 * Copyrights of the parts, see headers below.
15 *
16 *
17 * This program is free software; you can redistribute it and/or
18 * modify it under the terms of the GNU Lesser General Public
19 * License as published by the Free Software Foundation; either
20 * version 2.1 of the License, or (at your option) any later version.
21 *
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 * Lesser General Public License for more details.
26 *
27 * You should have received a copy of the GNU Lesser General Public
28 * License along with this library; if not, write to the Free Software
29 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
30 */
32 #include "decompress.h"
34 #define MIN(a, b) (((a) < (b)) ? (a) : (b))
36 static long long INIT read_int(unsigned char *ptr, int size)
37 {
38 int i;
39 long long ret = 0;
41 for (i = 0; i < size; i++)
42 ret = (ret << 8) | ptr[size-i-1];
43 return ret;
44 }
46 #define ENDIAN_CONVERT(x) \
47 x = (typeof(x))read_int((unsigned char *)&x, sizeof(x))
50 /* Small range coder implementation for lzma.
51 * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >
52 *
53 * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
54 * Copyright (c) 1999-2005 Igor Pavlov
55 */
57 #include <xen/compiler.h>
59 #define LZMA_IOBUF_SIZE 0x10000
61 struct rc {
62 int (*fill)(void*, unsigned int);
63 uint8_t *ptr;
64 uint8_t *buffer;
65 uint8_t *buffer_end;
66 int buffer_size;
67 uint32_t code;
68 uint32_t range;
69 uint32_t bound;
70 };
73 #define RC_TOP_BITS 24
74 #define RC_MOVE_BITS 5
75 #define RC_MODEL_TOTAL_BITS 11
78 static int nofill(void *buffer, unsigned int len)
79 {
80 return -1;
81 }
83 /* Called twice: once at startup and once in rc_normalize() */
84 static void INIT rc_read(struct rc *rc)
85 {
86 rc->buffer_size = rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE);
87 if (rc->buffer_size <= 0)
88 error("unexpected EOF");
89 rc->ptr = rc->buffer;
90 rc->buffer_end = rc->buffer + rc->buffer_size;
91 }
93 /* Called once */
94 static inline void INIT rc_init(struct rc *rc,
95 int (*fill)(void*, unsigned int),
96 unsigned char *buffer, int buffer_size)
97 {
98 if (fill)
99 rc->fill = fill;
100 else
101 rc->fill = nofill;
102 rc->buffer = (uint8_t *)buffer;
103 rc->buffer_size = buffer_size;
104 rc->buffer_end = rc->buffer + rc->buffer_size;
105 rc->ptr = rc->buffer;
107 rc->code = 0;
108 rc->range = 0xFFFFFFFF;
109 }
111 static inline void INIT rc_init_code(struct rc *rc)
112 {
113 int i;
115 for (i = 0; i < 5; i++) {
116 if (rc->ptr >= rc->buffer_end)
117 rc_read(rc);
118 rc->code = (rc->code << 8) | *rc->ptr++;
119 }
120 }
123 /* Called once. TODO: bb_maybe_free() */
124 static inline void INIT rc_free(struct rc *rc)
125 {
126 free(rc->buffer);
127 }
129 /* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */
130 static void INIT rc_do_normalize(struct rc *rc)
131 {
132 if (rc->ptr >= rc->buffer_end)
133 rc_read(rc);
134 rc->range <<= 8;
135 rc->code = (rc->code << 8) | *rc->ptr++;
136 }
137 static inline void INIT rc_normalize(struct rc *rc)
138 {
139 if (rc->range < (1 << RC_TOP_BITS))
140 rc_do_normalize(rc);
141 }
143 /* Called 9 times */
144 /* Why rc_is_bit_0_helper exists?
145 *Because we want to always expose (rc->code < rc->bound) to optimizer
146 */
147 static inline uint32_t INIT rc_is_bit_0_helper(struct rc *rc, uint16_t *p)
148 {
149 rc_normalize(rc);
150 rc->bound = *p * (rc->range >> RC_MODEL_TOTAL_BITS);
151 return rc->bound;
152 }
153 static inline int INIT rc_is_bit_0(struct rc *rc, uint16_t *p)
154 {
155 uint32_t t = rc_is_bit_0_helper(rc, p);
156 return rc->code < t;
157 }
159 /* Called ~10 times, but very small, thus inlined */
160 static inline void INIT rc_update_bit_0(struct rc *rc, uint16_t *p)
161 {
162 rc->range = rc->bound;
163 *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
164 }
165 static inline void rc_update_bit_1(struct rc *rc, uint16_t *p)
166 {
167 rc->range -= rc->bound;
168 rc->code -= rc->bound;
169 *p -= *p >> RC_MOVE_BITS;
170 }
172 /* Called 4 times in unlzma loop */
173 static int INIT rc_get_bit(struct rc *rc, uint16_t *p, int *symbol)
174 {
175 if (rc_is_bit_0(rc, p)) {
176 rc_update_bit_0(rc, p);
177 *symbol *= 2;
178 return 0;
179 } else {
180 rc_update_bit_1(rc, p);
181 *symbol = *symbol * 2 + 1;
182 return 1;
183 }
184 }
186 /* Called once */
187 static inline int INIT rc_direct_bit(struct rc *rc)
188 {
189 rc_normalize(rc);
190 rc->range >>= 1;
191 if (rc->code >= rc->range) {
192 rc->code -= rc->range;
193 return 1;
194 }
195 return 0;
196 }
198 /* Called twice */
199 static inline void INIT
200 rc_bit_tree_decode(struct rc *rc, uint16_t *p, int num_levels, int *symbol)
201 {
202 int i = num_levels;
204 *symbol = 1;
205 while (i--)
206 rc_get_bit(rc, p + *symbol, symbol);
207 *symbol -= 1 << num_levels;
208 }
211 /*
212 * Small lzma deflate implementation.
213 * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >
214 *
215 * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
216 * Copyright (C) 1999-2005 Igor Pavlov
217 */
220 struct lzma_header {
221 uint8_t pos;
222 uint32_t dict_size;
223 uint64_t dst_size;
224 } __attribute__ ((packed)) ;
227 #define LZMA_BASE_SIZE 1846
228 #define LZMA_LIT_SIZE 768
230 #define LZMA_NUM_POS_BITS_MAX 4
232 #define LZMA_LEN_NUM_LOW_BITS 3
233 #define LZMA_LEN_NUM_MID_BITS 3
234 #define LZMA_LEN_NUM_HIGH_BITS 8
236 #define LZMA_LEN_CHOICE 0
237 #define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1)
238 #define LZMA_LEN_LOW (LZMA_LEN_CHOICE_2 + 1)
239 #define LZMA_LEN_MID (LZMA_LEN_LOW \
240 + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS)))
241 #define LZMA_LEN_HIGH (LZMA_LEN_MID \
242 +(1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS)))
243 #define LZMA_NUM_LEN_PROBS (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS))
245 #define LZMA_NUM_STATES 12
246 #define LZMA_NUM_LIT_STATES 7
248 #define LZMA_START_POS_MODEL_INDEX 4
249 #define LZMA_END_POS_MODEL_INDEX 14
250 #define LZMA_NUM_FULL_DISTANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1))
252 #define LZMA_NUM_POS_SLOT_BITS 6
253 #define LZMA_NUM_LEN_TO_POS_STATES 4
255 #define LZMA_NUM_ALIGN_BITS 4
257 #define LZMA_MATCH_MIN_LEN 2
259 #define LZMA_IS_MATCH 0
260 #define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
261 #define LZMA_IS_REP_G0 (LZMA_IS_REP + LZMA_NUM_STATES)
262 #define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATES)
263 #define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES)
264 #define LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES)
265 #define LZMA_POS_SLOT (LZMA_IS_REP_0_LONG \
266 + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
267 #define LZMA_SPEC_POS (LZMA_POS_SLOT \
268 +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS))
269 #define LZMA_ALIGN (LZMA_SPEC_POS \
270 + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX)
271 #define LZMA_LEN_CODER (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS))
272 #define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS)
273 #define LZMA_LITERAL (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS)
276 struct writer {
277 uint8_t *buffer;
278 uint8_t previous_byte;
279 size_t buffer_pos;
280 int bufsize;
281 size_t global_pos;
282 int(*flush)(void*, unsigned int);
283 struct lzma_header *header;
284 };
286 struct cstate {
287 int state;
288 uint32_t rep0, rep1, rep2, rep3;
289 };
291 static inline size_t INIT get_pos(struct writer *wr)
292 {
293 return
294 wr->global_pos + wr->buffer_pos;
295 }
297 static inline uint8_t INIT peek_old_byte(struct writer *wr,
298 uint32_t offs)
299 {
300 if (!wr->flush) {
301 int32_t pos;
302 while (offs > wr->header->dict_size)
303 offs -= wr->header->dict_size;
304 pos = wr->buffer_pos - offs;
305 return wr->buffer[pos];
306 } else {
307 uint32_t pos = wr->buffer_pos - offs;
308 while (pos >= wr->header->dict_size)
309 pos += wr->header->dict_size;
310 return wr->buffer[pos];
311 }
313 }
315 static inline void INIT write_byte(struct writer *wr, uint8_t byte)
316 {
317 wr->buffer[wr->buffer_pos++] = wr->previous_byte = byte;
318 if (wr->flush && wr->buffer_pos == wr->header->dict_size) {
319 wr->buffer_pos = 0;
320 wr->global_pos += wr->header->dict_size;
321 wr->flush((char *)wr->buffer, wr->header->dict_size);
322 }
323 }
326 static inline void INIT copy_byte(struct writer *wr, uint32_t offs)
327 {
328 write_byte(wr, peek_old_byte(wr, offs));
329 }
331 static inline void INIT copy_bytes(struct writer *wr,
332 uint32_t rep0, int len)
333 {
334 do {
335 copy_byte(wr, rep0);
336 len--;
337 } while (len != 0 && wr->buffer_pos < wr->header->dst_size);
338 }
340 static inline void INIT process_bit0(struct writer *wr, struct rc *rc,
341 struct cstate *cst, uint16_t *p,
342 int pos_state, uint16_t *prob,
343 int lc, uint32_t literal_pos_mask) {
344 int mi = 1;
345 rc_update_bit_0(rc, prob);
346 prob = (p + LZMA_LITERAL +
347 (LZMA_LIT_SIZE
348 * (((get_pos(wr) & literal_pos_mask) << lc)
349 + (wr->previous_byte >> (8 - lc))))
350 );
352 if (cst->state >= LZMA_NUM_LIT_STATES) {
353 int match_byte = peek_old_byte(wr, cst->rep0);
354 do {
355 int bit;
356 uint16_t *prob_lit;
358 match_byte <<= 1;
359 bit = match_byte & 0x100;
360 prob_lit = prob + 0x100 + bit + mi;
361 if (rc_get_bit(rc, prob_lit, &mi)) {
362 if (!bit)
363 break;
364 } else {
365 if (bit)
366 break;
367 }
368 } while (mi < 0x100);
369 }
370 while (mi < 0x100) {
371 uint16_t *prob_lit = prob + mi;
372 rc_get_bit(rc, prob_lit, &mi);
373 }
374 write_byte(wr, mi);
375 if (cst->state < 4)
376 cst->state = 0;
377 else if (cst->state < 10)
378 cst->state -= 3;
379 else
380 cst->state -= 6;
381 }
383 static inline void INIT process_bit1(struct writer *wr, struct rc *rc,
384 struct cstate *cst, uint16_t *p,
385 int pos_state, uint16_t *prob) {
386 int offset;
387 uint16_t *prob_len;
388 int num_bits;
389 int len;
391 rc_update_bit_1(rc, prob);
392 prob = p + LZMA_IS_REP + cst->state;
393 if (rc_is_bit_0(rc, prob)) {
394 rc_update_bit_0(rc, prob);
395 cst->rep3 = cst->rep2;
396 cst->rep2 = cst->rep1;
397 cst->rep1 = cst->rep0;
398 cst->state = cst->state < LZMA_NUM_LIT_STATES ? 0 : 3;
399 prob = p + LZMA_LEN_CODER;
400 } else {
401 rc_update_bit_1(rc, prob);
402 prob = p + LZMA_IS_REP_G0 + cst->state;
403 if (rc_is_bit_0(rc, prob)) {
404 rc_update_bit_0(rc, prob);
405 prob = (p + LZMA_IS_REP_0_LONG
406 + (cst->state <<
407 LZMA_NUM_POS_BITS_MAX) +
408 pos_state);
409 if (rc_is_bit_0(rc, prob)) {
410 rc_update_bit_0(rc, prob);
412 cst->state = cst->state < LZMA_NUM_LIT_STATES ?
413 9 : 11;
414 copy_byte(wr, cst->rep0);
415 return;
416 } else {
417 rc_update_bit_1(rc, prob);
418 }
419 } else {
420 uint32_t distance;
422 rc_update_bit_1(rc, prob);
423 prob = p + LZMA_IS_REP_G1 + cst->state;
424 if (rc_is_bit_0(rc, prob)) {
425 rc_update_bit_0(rc, prob);
426 distance = cst->rep1;
427 } else {
428 rc_update_bit_1(rc, prob);
429 prob = p + LZMA_IS_REP_G2 + cst->state;
430 if (rc_is_bit_0(rc, prob)) {
431 rc_update_bit_0(rc, prob);
432 distance = cst->rep2;
433 } else {
434 rc_update_bit_1(rc, prob);
435 distance = cst->rep3;
436 cst->rep3 = cst->rep2;
437 }
438 cst->rep2 = cst->rep1;
439 }
440 cst->rep1 = cst->rep0;
441 cst->rep0 = distance;
442 }
443 cst->state = cst->state < LZMA_NUM_LIT_STATES ? 8 : 11;
444 prob = p + LZMA_REP_LEN_CODER;
445 }
447 prob_len = prob + LZMA_LEN_CHOICE;
448 if (rc_is_bit_0(rc, prob_len)) {
449 rc_update_bit_0(rc, prob_len);
450 prob_len = (prob + LZMA_LEN_LOW
451 + (pos_state <<
452 LZMA_LEN_NUM_LOW_BITS));
453 offset = 0;
454 num_bits = LZMA_LEN_NUM_LOW_BITS;
455 } else {
456 rc_update_bit_1(rc, prob_len);
457 prob_len = prob + LZMA_LEN_CHOICE_2;
458 if (rc_is_bit_0(rc, prob_len)) {
459 rc_update_bit_0(rc, prob_len);
460 prob_len = (prob + LZMA_LEN_MID
461 + (pos_state <<
462 LZMA_LEN_NUM_MID_BITS));
463 offset = 1 << LZMA_LEN_NUM_LOW_BITS;
464 num_bits = LZMA_LEN_NUM_MID_BITS;
465 } else {
466 rc_update_bit_1(rc, prob_len);
467 prob_len = prob + LZMA_LEN_HIGH;
468 offset = ((1 << LZMA_LEN_NUM_LOW_BITS)
469 + (1 << LZMA_LEN_NUM_MID_BITS));
470 num_bits = LZMA_LEN_NUM_HIGH_BITS;
471 }
472 }
474 rc_bit_tree_decode(rc, prob_len, num_bits, &len);
475 len += offset;
477 if (cst->state < 4) {
478 int pos_slot;
480 cst->state += LZMA_NUM_LIT_STATES;
481 prob =
482 p + LZMA_POS_SLOT +
483 ((len <
484 LZMA_NUM_LEN_TO_POS_STATES ? len :
485 LZMA_NUM_LEN_TO_POS_STATES - 1)
486 << LZMA_NUM_POS_SLOT_BITS);
487 rc_bit_tree_decode(rc, prob,
488 LZMA_NUM_POS_SLOT_BITS,
489 &pos_slot);
490 if (pos_slot >= LZMA_START_POS_MODEL_INDEX) {
491 int i, mi;
492 num_bits = (pos_slot >> 1) - 1;
493 cst->rep0 = 2 | (pos_slot & 1);
494 if (pos_slot < LZMA_END_POS_MODEL_INDEX) {
495 cst->rep0 <<= num_bits;
496 prob = p + LZMA_SPEC_POS +
497 cst->rep0 - pos_slot - 1;
498 } else {
499 num_bits -= LZMA_NUM_ALIGN_BITS;
500 while (num_bits--)
501 cst->rep0 = (cst->rep0 << 1) |
502 rc_direct_bit(rc);
503 prob = p + LZMA_ALIGN;
504 cst->rep0 <<= LZMA_NUM_ALIGN_BITS;
505 num_bits = LZMA_NUM_ALIGN_BITS;
506 }
507 i = 1;
508 mi = 1;
509 while (num_bits--) {
510 if (rc_get_bit(rc, prob + mi, &mi))
511 cst->rep0 |= i;
512 i <<= 1;
513 }
514 } else
515 cst->rep0 = pos_slot;
516 if (++(cst->rep0) == 0)
517 return;
518 }
520 len += LZMA_MATCH_MIN_LEN;
522 copy_bytes(wr, cst->rep0, len);
523 }
527 STATIC int INIT unlzma(unsigned char *buf, unsigned int in_len,
528 int(*fill)(void*, unsigned int),
529 int(*flush)(void*, unsigned int),
530 unsigned char *output,
531 unsigned int *posp,
532 void(*error_fn)(const char *x)
533 )
534 {
535 struct lzma_header header;
536 int lc, pb, lp;
537 uint32_t pos_state_mask;
538 uint32_t literal_pos_mask;
539 uint16_t *p;
540 int num_probs;
541 struct rc rc;
542 int i, mi;
543 struct writer wr;
544 struct cstate cst;
545 unsigned char *inbuf;
546 int ret = -1;
548 set_error_fn(error_fn);
550 if (buf)
551 inbuf = buf;
552 else
553 inbuf = malloc(LZMA_IOBUF_SIZE);
554 if (!inbuf) {
555 error("Could not allocate input bufer");
556 goto exit_0;
557 }
559 cst.state = 0;
560 cst.rep0 = cst.rep1 = cst.rep2 = cst.rep3 = 1;
562 wr.header = &header;
563 wr.flush = flush;
564 wr.global_pos = 0;
565 wr.previous_byte = 0;
566 wr.buffer_pos = 0;
568 rc_init(&rc, fill, inbuf, in_len);
570 for (i = 0; i < sizeof(header); i++) {
571 if (rc.ptr >= rc.buffer_end)
572 rc_read(&rc);
573 ((unsigned char *)&header)[i] = *rc.ptr++;
574 }
576 if (header.pos >= (9 * 5 * 5))
577 error("bad header");
579 mi = 0;
580 lc = header.pos;
581 while (lc >= 9) {
582 mi++;
583 lc -= 9;
584 }
585 pb = 0;
586 lp = mi;
587 while (lp >= 5) {
588 pb++;
589 lp -= 5;
590 }
591 pos_state_mask = (1 << pb) - 1;
592 literal_pos_mask = (1 << lp) - 1;
594 ENDIAN_CONVERT(header.dict_size);
595 ENDIAN_CONVERT(header.dst_size);
597 if (header.dict_size == 0)
598 header.dict_size = 1;
600 if (output)
601 wr.buffer = output;
602 else {
603 wr.bufsize = MIN(header.dst_size, header.dict_size);
604 wr.buffer = large_malloc(wr.bufsize);
605 }
606 if (wr.buffer == NULL)
607 goto exit_1;
609 num_probs = LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp));
610 p = (uint16_t *) large_malloc(num_probs * sizeof(*p));
611 if (p == 0)
612 goto exit_2;
613 num_probs = LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp));
614 for (i = 0; i < num_probs; i++)
615 p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1;
617 rc_init_code(&rc);
619 while (get_pos(&wr) < header.dst_size) {
620 int pos_state = get_pos(&wr) & pos_state_mask;
621 uint16_t *prob = p + LZMA_IS_MATCH +
622 (cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state;
623 if (rc_is_bit_0(&rc, prob))
624 process_bit0(&wr, &rc, &cst, p, pos_state, prob,
625 lc, literal_pos_mask);
626 else {
627 process_bit1(&wr, &rc, &cst, p, pos_state, prob);
628 if (cst.rep0 == 0)
629 break;
630 }
631 }
633 if (posp)
634 *posp = rc.ptr-rc.buffer;
635 if (wr.flush)
636 wr.flush(wr.buffer, wr.buffer_pos);
637 ret = 0;
638 large_free(p);
639 exit_2:
640 if (!output)
641 large_free(wr.buffer);
642 exit_1:
643 if (!buf)
644 free(inbuf);
645 exit_0:
646 return ret;
647 }