arch/x86/boot/compressed/misc.c

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