misc.c 8.8 KB
Newer Older
L
Linus Torvalds 已提交
1 2
/*
 * misc.c
3 4
 *
 * This is a collection of several routines from gzip-1.0.3
L
Linus Torvalds 已提交
5 6 7 8 9 10 11
 * adapted for Linux.
 *
 * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
 * puts by Nick Holloway 1993, better puts by Martin Mares 1995
 * High loaded stuff by Hans Lermen & Werner Almesberger, Feb. 1996
 */

12
#include "misc.h"
13 14 15 16 17 18 19 20 21

/* WARNING!!
 * This code is compiled with -fPIC and it is relocated dynamically
 * at run time, but no relocation processing is performed.
 * This means that it is not safe to place pointers in static structures.
 */

/*
 * Getting to provable safe in place decompression is hard.
S
Simon Arlott 已提交
22
 * Worst case behaviours need to be analyzed.
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
 * Background information:
 *
 * The file layout is:
 *    magic[2]
 *    method[1]
 *    flags[1]
 *    timestamp[4]
 *    extraflags[1]
 *    os[1]
 *    compressed data blocks[N]
 *    crc[4] orig_len[4]
 *
 * resulting in 18 bytes of non compressed data overhead.
 *
 * Files divided into blocks
 * 1 bit (last block flag)
 * 2 bits (block type)
 *
41 42
 * 1 block occurs every 32K -1 bytes or when there 50% compression
 * has been achieved. The smallest block type encoding is always used.
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
 *
 * stored:
 *    32 bits length in bytes.
 *
 * fixed:
 *    magic fixed tree.
 *    symbols.
 *
 * dynamic:
 *    dynamic tree encoding.
 *    symbols.
 *
 *
 * The buffer for decompression in place is the length of the
 * uncompressed data, plus a small amount extra to keep the algorithm safe.
 * The compressed data is placed at the end of the buffer.  The output
 * pointer is placed at the start of the buffer and the input pointer
 * is placed where the compressed data starts.  Problems will occur
 * when the output pointer overruns the input pointer.
 *
 * The output pointer can only overrun the input pointer if the input
 * pointer is moving faster than the output pointer.  A condition only
 * triggered by data whose compressed form is larger than the uncompressed
 * form.
 *
 * The worst case at the block level is a growth of the compressed data
 * of 5 bytes per 32767 bytes.
 *
 * The worst case internal to a compressed block is very hard to figure.
 * The worst case can at least be boundined by having one bit that represents
 * 32764 bytes and then all of the rest of the bytes representing the very
 * very last byte.
 *
 * All of which is enough to compute an amount of extra data that is required
 * to be safe.  To avoid problems at the block level allocating 5 extra bytes
78 79 80
 * per 32767 bytes of data is sufficient.  To avoind problems internal to a
 * block adding an extra 32767 bytes (the worst case uncompressed block size)
 * is sufficient, to ensure that in the worst case the decompressed data for
81 82 83 84 85 86 87 88 89 90
 * block will stop the byte before the compressed data for a block begins.
 * To avoid problems with the compressed data's meta information an extra 18
 * bytes are needed.  Leading to the formula:
 *
 * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
 *
 * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
 * Adding 32768 instead of 32767 just makes for round numbers.
 * Adding the decompressor_size is necessary as it musht live after all
 * of the data as well.  Last I measured the decompressor is about 14K.
S
Simon Arlott 已提交
91
 * 10K of actual data and 4K of bss.
92 93
 *
 */
L
Linus Torvalds 已提交
94 95 96 97

/*
 * gzip declarations
 */
98
#define STATIC		static
L
Linus Torvalds 已提交
99 100 101

#undef memset
#undef memcpy
102
#define memzero(s, n)	memset((s), 0, (n))
L
Linus Torvalds 已提交
103 104 105


static void error(char *m);
106

L
Linus Torvalds 已提交
107 108 109
/*
 * This is set up by the setup-routine at boot-time
 */
110 111
struct boot_params *real_mode;		/* Pointer to real-mode data */
static int debug;
L
Linus Torvalds 已提交
112

B
Brian Gerst 已提交
113 114
void *memset(void *s, int c, size_t n);
void *memcpy(void *dest, const void *src, size_t n);
115

116 117 118 119 120 121 122 123
#ifdef CONFIG_X86_64
#define memptr long
#else
#define memptr unsigned
#endif

static memptr free_mem_ptr;
static memptr free_mem_end_ptr;
L
Linus Torvalds 已提交
124

125
static char *vidmem;
L
Linus Torvalds 已提交
126 127 128
static int vidport;
static int lines, cols;

129 130 131 132 133 134 135 136 137 138 139
#ifdef CONFIG_KERNEL_GZIP
#include "../../../../lib/decompress_inflate.c"
#endif

#ifdef CONFIG_KERNEL_BZIP2
#include "../../../../lib/decompress_bunzip2.c"
#endif

#ifdef CONFIG_KERNEL_LZMA
#include "../../../../lib/decompress_unlzma.c"
#endif
L
Linus Torvalds 已提交
140

L
Lasse Collin 已提交
141 142 143 144
#ifdef CONFIG_KERNEL_XZ
#include "../../../../lib/decompress_unxz.c"
#endif

145 146 147 148
#ifdef CONFIG_KERNEL_LZO
#include "../../../../lib/decompress_unlzo.c"
#endif

L
Linus Torvalds 已提交
149 150 151 152
static void scroll(void)
{
	int i;

153 154
	memcpy(vidmem, vidmem + cols * 2, (lines - 1) * cols * 2);
	for (i = (lines - 1) * cols * 2; i < lines * cols * 2; i += 2)
L
Linus Torvalds 已提交
155 156 157
		vidmem[i] = ' ';
}

158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
#define XMTRDY          0x20

#define TXR             0       /*  Transmit register (WRITE) */
#define LSR             5       /*  Line Status               */
static void serial_putchar(int ch)
{
	unsigned timeout = 0xffff;

	while ((inb(early_serial_base + LSR) & XMTRDY) == 0 && --timeout)
		cpu_relax();

	outb(ch, early_serial_base + TXR);
}

void __putstr(int error, const char *s)
L
Linus Torvalds 已提交
173
{
174
	int x, y, pos;
L
Linus Torvalds 已提交
175 176
	char c;

177 178 179 180
#ifndef CONFIG_X86_VERBOSE_BOOTUP
	if (!error)
		return;
#endif
181 182 183 184 185 186 187 188
	if (early_serial_base) {
		const char *str = s;
		while (*str) {
			if (*str == '\n')
				serial_putchar('\r');
			serial_putchar(*str++);
		}
	}
189

190 191
	if (real_mode->screen_info.orig_video_mode == 0 &&
	    lines == 0 && cols == 0)
R
Rusty Russell 已提交
192 193
		return;

194 195
	x = real_mode->screen_info.orig_x;
	y = real_mode->screen_info.orig_y;
L
Linus Torvalds 已提交
196

197 198
	while ((c = *s++) != '\0') {
		if (c == '\n') {
L
Linus Torvalds 已提交
199
			x = 0;
200
			if (++y >= lines) {
L
Linus Torvalds 已提交
201 202 203 204
				scroll();
				y--;
			}
		} else {
205
			vidmem[(x + cols * y) * 2] = c;
206
			if (++x >= cols) {
L
Linus Torvalds 已提交
207
				x = 0;
208
				if (++y >= lines) {
L
Linus Torvalds 已提交
209 210 211 212 213 214 215
					scroll();
					y--;
				}
			}
		}
	}

216 217
	real_mode->screen_info.orig_x = x;
	real_mode->screen_info.orig_y = y;
L
Linus Torvalds 已提交
218 219

	pos = (x + cols * y) * 2;	/* Update cursor position */
220 221 222 223
	outb(14, vidport);
	outb(0xff & (pos >> 9), vidport+1);
	outb(15, vidport);
	outb(0xff & (pos >> 1), vidport+1);
L
Linus Torvalds 已提交
224 225
}

226 227 228 229 230 231
static void debug_putstr(const char *s)
{
	if (debug)
		putstr(s);
}

B
Brian Gerst 已提交
232
void *memset(void *s, int c, size_t n)
L
Linus Torvalds 已提交
233 234
{
	int i;
J
Jan Engelhardt 已提交
235
	char *ss = s;
L
Linus Torvalds 已提交
236

237 238
	for (i = 0; i < n; i++)
		ss[i] = c;
L
Linus Torvalds 已提交
239 240
	return s;
}
241
#ifdef CONFIG_X86_32
B
Brian Gerst 已提交
242
void *memcpy(void *dest, const void *src, size_t n)
L
Linus Torvalds 已提交
243
{
244 245 246 247 248 249 250 251
	int d0, d1, d2;
	asm volatile(
		"rep ; movsl\n\t"
		"movl %4,%%ecx\n\t"
		"rep ; movsb\n\t"
		: "=&c" (d0), "=&D" (d1), "=&S" (d2)
		: "0" (n >> 2), "g" (n & 3), "1" (dest), "2" (src)
		: "memory");
L
Linus Torvalds 已提交
252

253
	return dest;
L
Linus Torvalds 已提交
254
}
255 256 257 258 259 260 261 262 263 264 265
#else
void *memcpy(void *dest, const void *src, size_t n)
{
	long d0, d1, d2;
	asm volatile(
		"rep ; movsq\n\t"
		"movq %4,%%rcx\n\t"
		"rep ; movsb\n\t"
		: "=&c" (d0), "=&D" (d1), "=&S" (d2)
		: "0" (n >> 3), "g" (n & 7), "1" (dest), "2" (src)
		: "memory");
L
Linus Torvalds 已提交
266

267 268 269
	return dest;
}
#endif
L
Linus Torvalds 已提交
270 271 272

static void error(char *x)
{
273 274 275
	__putstr(1, "\n\n");
	__putstr(1, x);
	__putstr(1, "\n\n -- System halted");
L
Linus Torvalds 已提交
276

I
Ingo Molnar 已提交
277 278
	while (1)
		asm("hlt");
L
Linus Torvalds 已提交
279 280
}

281 282 283 284 285 286 287 288 289 290 291 292 293
static void parse_elf(void *output)
{
#ifdef CONFIG_X86_64
	Elf64_Ehdr ehdr;
	Elf64_Phdr *phdrs, *phdr;
#else
	Elf32_Ehdr ehdr;
	Elf32_Phdr *phdrs, *phdr;
#endif
	void *dest;
	int i;

	memcpy(&ehdr, output, sizeof(ehdr));
294
	if (ehdr.e_ident[EI_MAG0] != ELFMAG0 ||
295 296
	   ehdr.e_ident[EI_MAG1] != ELFMAG1 ||
	   ehdr.e_ident[EI_MAG2] != ELFMAG2 ||
297
	   ehdr.e_ident[EI_MAG3] != ELFMAG3) {
298 299 300 301
		error("Kernel is not a valid ELF file");
		return;
	}

302
	debug_putstr("Parsing ELF... ");
303 304 305 306 307 308 309

	phdrs = malloc(sizeof(*phdrs) * ehdr.e_phnum);
	if (!phdrs)
		error("Failed to allocate space for phdrs");

	memcpy(phdrs, output + ehdr.e_phoff, sizeof(*phdrs) * ehdr.e_phnum);

310
	for (i = 0; i < ehdr.e_phnum; i++) {
311 312 313 314 315 316 317 318
		phdr = &phdrs[i];

		switch (phdr->p_type) {
		case PT_LOAD:
#ifdef CONFIG_RELOCATABLE
			dest = output;
			dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR);
#else
319
			dest = (void *)(phdr->p_paddr);
320 321 322 323 324 325 326 327
#endif
			memcpy(dest,
			       output + phdr->p_offset,
			       phdr->p_filesz);
			break;
		default: /* Ignore other PT_* */ break;
		}
	}
328 329

	free(phdrs);
330 331
}

332
asmlinkage void decompress_kernel(void *rmode, memptr heap,
333 334 335
				  unsigned char *input_data,
				  unsigned long input_len,
				  unsigned char *output)
L
Linus Torvalds 已提交
336 337 338
{
	real_mode = rmode;

339 340
	if (cmdline_find_option_bool("debug"))
		debug = 1;
341

342
	if (real_mode->screen_info.orig_video_mode == 7) {
L
Linus Torvalds 已提交
343 344 345 346 347 348 349
		vidmem = (char *) 0xb0000;
		vidport = 0x3b4;
	} else {
		vidmem = (char *) 0xb8000;
		vidport = 0x3d4;
	}

350 351
	lines = real_mode->screen_info.orig_video_lines;
	cols = real_mode->screen_info.orig_video_cols;
L
Linus Torvalds 已提交
352

353
	console_init();
354
	debug_putstr("early console in decompress_kernel\n");
355

356
	free_mem_ptr     = heap;	/* Heap */
357
	free_mem_end_ptr = heap + BOOT_HEAP_SIZE;
358

359 360
	if ((unsigned long)output & (MIN_KERNEL_ALIGN - 1))
		error("Destination address inappropriately aligned");
361
#ifdef CONFIG_X86_64
362
	if (heap > 0x3fffffffffffUL)
363 364
		error("Destination address too large");
#else
365
	if (heap > ((-__PAGE_OFFSET-(128<<20)-1) & 0x7fffffff))
366
		error("Destination address too large");
367
#endif
368
#ifndef CONFIG_RELOCATABLE
369
	if ((unsigned long)output != LOAD_PHYSICAL_ADDR)
370 371
		error("Wrong destination address");
#endif
L
Linus Torvalds 已提交
372

373
	debug_putstr("\nDecompressing Linux... ");
374
	decompress(input_data, input_len, NULL, NULL, output, NULL, error);
375
	parse_elf(output);
376
	debug_putstr("done.\nBooting the kernel.\n");
377
	return;
L
Linus Torvalds 已提交
378
}