Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
misc.c
Go to the documentation of this file.
1 /*
2  * misc.c
3  *
4  * This is a collection of several routines from gzip-1.0.3
5  * adapted for Linux.
6  *
7  * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
8  * puts by Nick Holloway 1993, better puts by Martin Mares 1995
9  * High loaded stuff by Hans Lermen & Werner Almesberger, Feb. 1996
10  */
11 
12 #include "misc.h"
13 
14 /* WARNING!!
15  * This code is compiled with -fPIC and it is relocated dynamically
16  * at run time, but no relocation processing is performed.
17  * This means that it is not safe to place pointers in static structures.
18  */
19 
20 /*
21  * Getting to provable safe in place decompression is hard.
22  * Worst case behaviours need to be analyzed.
23  * Background information:
24  *
25  * The file layout is:
26  * magic[2]
27  * method[1]
28  * flags[1]
29  * timestamp[4]
30  * extraflags[1]
31  * os[1]
32  * compressed data blocks[N]
33  * crc[4] orig_len[4]
34  *
35  * resulting in 18 bytes of non compressed data overhead.
36  *
37  * Files divided into blocks
38  * 1 bit (last block flag)
39  * 2 bits (block type)
40  *
41  * 1 block occurs every 32K -1 bytes or when there 50% compression
42  * has been achieved. The smallest block type encoding is always used.
43  *
44  * stored:
45  * 32 bits length in bytes.
46  *
47  * fixed:
48  * magic fixed tree.
49  * symbols.
50  *
51  * dynamic:
52  * dynamic tree encoding.
53  * symbols.
54  *
55  *
56  * The buffer for decompression in place is the length of the
57  * uncompressed data, plus a small amount extra to keep the algorithm safe.
58  * The compressed data is placed at the end of the buffer. The output
59  * pointer is placed at the start of the buffer and the input pointer
60  * is placed where the compressed data starts. Problems will occur
61  * when the output pointer overruns the input pointer.
62  *
63  * The output pointer can only overrun the input pointer if the input
64  * pointer is moving faster than the output pointer. A condition only
65  * triggered by data whose compressed form is larger than the uncompressed
66  * form.
67  *
68  * The worst case at the block level is a growth of the compressed data
69  * of 5 bytes per 32767 bytes.
70  *
71  * The worst case internal to a compressed block is very hard to figure.
72  * The worst case can at least be boundined by having one bit that represents
73  * 32764 bytes and then all of the rest of the bytes representing the very
74  * very last byte.
75  *
76  * All of which is enough to compute an amount of extra data that is required
77  * to be safe. To avoid problems at the block level allocating 5 extra bytes
78  * per 32767 bytes of data is sufficient. To avoind problems internal to a
79  * block adding an extra 32767 bytes (the worst case uncompressed block size)
80  * is sufficient, to ensure that in the worst case the decompressed data for
81  * block will stop the byte before the compressed data for a block begins.
82  * To avoid problems with the compressed data's meta information an extra 18
83  * bytes are needed. Leading to the formula:
84  *
85  * extra_bytes = (uncompressed_size >> 12) + 32768 + 18 + decompressor_size.
86  *
87  * Adding 8 bytes per 32K is a bit excessive but much easier to calculate.
88  * Adding 32768 instead of 32767 just makes for round numbers.
89  * Adding the decompressor_size is necessary as it musht live after all
90  * of the data as well. Last I measured the decompressor is about 14K.
91  * 10K of actual data and 4K of bss.
92  *
93  */
94 
95 /*
96  * gzip declarations
97  */
98 #define STATIC static
99 
100 #undef memset
101 #undef memcpy
102 #define memzero(s, n) memset((s), 0, (n))
103 
104 
105 static void error(char *m);
106 
107 /*
108  * This is set up by the setup-routine at boot-time
109  */
110 struct boot_params *real_mode; /* Pointer to real-mode data */
111 
112 void *memset(void *s, int c, size_t n);
113 void *memcpy(void *dest, const void *src, size_t n);
114 
115 #ifdef CONFIG_X86_64
116 #define memptr long
117 #else
118 #define memptr unsigned
119 #endif
120 
121 static memptr free_mem_ptr;
122 static memptr free_mem_end_ptr;
123 
124 static char *vidmem;
125 static int vidport;
126 static int lines, cols;
127 
128 #ifdef CONFIG_KERNEL_GZIP
129 #include "../../../../lib/decompress_inflate.c"
130 #endif
131 
132 #ifdef CONFIG_KERNEL_BZIP2
133 #include "../../../../lib/decompress_bunzip2.c"
134 #endif
135 
136 #ifdef CONFIG_KERNEL_LZMA
137 #include "../../../../lib/decompress_unlzma.c"
138 #endif
139 
140 #ifdef CONFIG_KERNEL_XZ
141 #include "../../../../lib/decompress_unxz.c"
142 #endif
143 
144 #ifdef CONFIG_KERNEL_LZO
145 #include "../../../../lib/decompress_unlzo.c"
146 #endif
147 
148 static void scroll(void)
149 {
150  int i;
151 
152  memcpy(vidmem, vidmem + cols * 2, (lines - 1) * cols * 2);
153  for (i = (lines - 1) * cols * 2; i < lines * cols * 2; i += 2)
154  vidmem[i] = ' ';
155 }
156 
157 #define XMTRDY 0x20
158 
159 #define TXR 0 /* Transmit register (WRITE) */
160 #define LSR 5 /* Line Status */
161 static void serial_putchar(int ch)
162 {
163  unsigned timeout = 0xffff;
164 
165  while ((inb(early_serial_base + LSR) & XMTRDY) == 0 && --timeout)
166  cpu_relax();
167 
168  outb(ch, early_serial_base + TXR);
169 }
170 
171 void __putstr(const char *s)
172 {
173  int x, y, pos;
174  char c;
175 
176  if (early_serial_base) {
177  const char *str = s;
178  while (*str) {
179  if (*str == '\n')
180  serial_putchar('\r');
181  serial_putchar(*str++);
182  }
183  }
184 
185  if (real_mode->screen_info.orig_video_mode == 0 &&
186  lines == 0 && cols == 0)
187  return;
188 
189  x = real_mode->screen_info.orig_x;
190  y = real_mode->screen_info.orig_y;
191 
192  while ((c = *s++) != '\0') {
193  if (c == '\n') {
194  x = 0;
195  if (++y >= lines) {
196  scroll();
197  y--;
198  }
199  } else {
200  vidmem[(x + cols * y) * 2] = c;
201  if (++x >= cols) {
202  x = 0;
203  if (++y >= lines) {
204  scroll();
205  y--;
206  }
207  }
208  }
209  }
210 
211  real_mode->screen_info.orig_x = x;
212  real_mode->screen_info.orig_y = y;
213 
214  pos = (x + cols * y) * 2; /* Update cursor position */
215  outb(14, vidport);
216  outb(0xff & (pos >> 9), vidport+1);
217  outb(15, vidport);
218  outb(0xff & (pos >> 1), vidport+1);
219 }
220 
221 void *memset(void *s, int c, size_t n)
222 {
223  int i;
224  char *ss = s;
225 
226  for (i = 0; i < n; i++)
227  ss[i] = c;
228  return s;
229 }
230 #ifdef CONFIG_X86_32
231 void *memcpy(void *dest, const void *src, size_t n)
232 {
233  int d0, d1, d2;
234  asm volatile(
235  "rep ; movsl\n\t"
236  "movl %4,%%ecx\n\t"
237  "rep ; movsb\n\t"
238  : "=&c" (d0), "=&D" (d1), "=&S" (d2)
239  : "0" (n >> 2), "g" (n & 3), "1" (dest), "2" (src)
240  : "memory");
241 
242  return dest;
243 }
244 #else
245 void *memcpy(void *dest, const void *src, size_t n)
246 {
247  long d0, d1, d2;
248  asm volatile(
249  "rep ; movsq\n\t"
250  "movq %4,%%rcx\n\t"
251  "rep ; movsb\n\t"
252  : "=&c" (d0), "=&D" (d1), "=&S" (d2)
253  : "0" (n >> 3), "g" (n & 7), "1" (dest), "2" (src)
254  : "memory");
255 
256  return dest;
257 }
258 #endif
259 
260 static void error(char *x)
261 {
262  error_putstr("\n\n");
263  error_putstr(x);
264  error_putstr("\n\n -- System halted");
265 
266  while (1)
267  asm("hlt");
268 }
269 
270 static void parse_elf(void *output)
271 {
272 #ifdef CONFIG_X86_64
273  Elf64_Ehdr ehdr;
274  Elf64_Phdr *phdrs, *phdr;
275 #else
276  Elf32_Ehdr ehdr;
277  Elf32_Phdr *phdrs, *phdr;
278 #endif
279  void *dest;
280  int i;
281 
282  memcpy(&ehdr, output, sizeof(ehdr));
283  if (ehdr.e_ident[EI_MAG0] != ELFMAG0 ||
284  ehdr.e_ident[EI_MAG1] != ELFMAG1 ||
285  ehdr.e_ident[EI_MAG2] != ELFMAG2 ||
286  ehdr.e_ident[EI_MAG3] != ELFMAG3) {
287  error("Kernel is not a valid ELF file");
288  return;
289  }
290 
291  debug_putstr("Parsing ELF... ");
292 
293  phdrs = malloc(sizeof(*phdrs) * ehdr.e_phnum);
294  if (!phdrs)
295  error("Failed to allocate space for phdrs");
296 
297  memcpy(phdrs, output + ehdr.e_phoff, sizeof(*phdrs) * ehdr.e_phnum);
298 
299  for (i = 0; i < ehdr.e_phnum; i++) {
300  phdr = &phdrs[i];
301 
302  switch (phdr->p_type) {
303  case PT_LOAD:
304 #ifdef CONFIG_RELOCATABLE
305  dest = output;
306  dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR);
307 #else
308  dest = (void *)(phdr->p_paddr);
309 #endif
310  memcpy(dest,
311  output + phdr->p_offset,
312  phdr->p_filesz);
313  break;
314  default: /* Ignore other PT_* */ break;
315  }
316  }
317 
318  free(phdrs);
319 }
320 
321 asmlinkage void decompress_kernel(void *rmode, memptr heap,
322  unsigned char *input_data,
323  unsigned long input_len,
324  unsigned char *output)
325 {
326  real_mode = rmode;
327 
328  if (real_mode->screen_info.orig_video_mode == 7) {
329  vidmem = (char *) 0xb0000;
330  vidport = 0x3b4;
331  } else {
332  vidmem = (char *) 0xb8000;
333  vidport = 0x3d4;
334  }
335 
336  lines = real_mode->screen_info.orig_video_lines;
337  cols = real_mode->screen_info.orig_video_cols;
338 
339  console_init();
340  debug_putstr("early console in decompress_kernel\n");
341 
342  free_mem_ptr = heap; /* Heap */
343  free_mem_end_ptr = heap + BOOT_HEAP_SIZE;
344 
345  if ((unsigned long)output & (MIN_KERNEL_ALIGN - 1))
346  error("Destination address inappropriately aligned");
347 #ifdef CONFIG_X86_64
348  if (heap > 0x3fffffffffffUL)
349  error("Destination address too large");
350 #else
351  if (heap > ((-__PAGE_OFFSET-(128<<20)-1) & 0x7fffffff))
352  error("Destination address too large");
353 #endif
354 #ifndef CONFIG_RELOCATABLE
355  if ((unsigned long)output != LOAD_PHYSICAL_ADDR)
356  error("Wrong destination address");
357 #endif
358 
359  debug_putstr("\nDecompressing Linux... ");
360  decompress(input_data, input_len, NULL, NULL, output, NULL, error);
361  parse_elf(output);
362  debug_putstr("done.\nBooting the kernel.\n");
363  return;
364 }