update
[qemu] / exec.c
1 /*
2  *  virtual page mapping and translated block handling
3  * 
4  *  Copyright (c) 2003 Fabrice Bellard
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this library; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19  */
20 #include <stdlib.h>
21 #include <stdio.h>
22 #include <stdarg.h>
23 #include <string.h>
24 #include <errno.h>
25 #include <unistd.h>
26 #include <inttypes.h>
27 #include <sys/mman.h>
28
29 #include "config.h"
30 #ifdef TARGET_I386
31 #include "cpu-i386.h"
32 #endif
33 #ifdef TARGET_ARM
34 #include "cpu-arm.h"
35 #endif
36 #include "exec.h"
37
38 //#define DEBUG_TB_INVALIDATE
39 //#define DEBUG_FLUSH
40
41 /* make various TB consistency checks */
42 //#define DEBUG_TB_CHECK 
43
44 /* threshold to flush the translated code buffer */
45 #define CODE_GEN_BUFFER_MAX_SIZE (CODE_GEN_BUFFER_SIZE - CODE_GEN_MAX_SIZE)
46
47 #define CODE_GEN_MAX_BLOCKS    (CODE_GEN_BUFFER_SIZE / 64)
48
49 TranslationBlock tbs[CODE_GEN_MAX_BLOCKS];
50 TranslationBlock *tb_hash[CODE_GEN_HASH_SIZE];
51 int nb_tbs;
52 /* any access to the tbs or the page table must use this lock */
53 spinlock_t tb_lock = SPIN_LOCK_UNLOCKED;
54
55 uint8_t code_gen_buffer[CODE_GEN_BUFFER_SIZE];
56 uint8_t *code_gen_ptr;
57
58 /* XXX: pack the flags in the low bits of the pointer ? */
59 typedef struct PageDesc {
60     unsigned long flags;
61     TranslationBlock *first_tb;
62 } PageDesc;
63
64 #define L2_BITS 10
65 #define L1_BITS (32 - L2_BITS - TARGET_PAGE_BITS)
66
67 #define L1_SIZE (1 << L1_BITS)
68 #define L2_SIZE (1 << L2_BITS)
69
70 static void tb_invalidate_page(unsigned long address);
71
72 unsigned long real_host_page_size;
73 unsigned long host_page_bits;
74 unsigned long host_page_size;
75 unsigned long host_page_mask;
76
77 static PageDesc *l1_map[L1_SIZE];
78
79 static void page_init(void)
80 {
81     /* NOTE: we can always suppose that host_page_size >=
82        TARGET_PAGE_SIZE */
83     real_host_page_size = getpagesize();
84     if (host_page_size == 0)
85         host_page_size = real_host_page_size;
86     if (host_page_size < TARGET_PAGE_SIZE)
87         host_page_size = TARGET_PAGE_SIZE;
88     host_page_bits = 0;
89     while ((1 << host_page_bits) < host_page_size)
90         host_page_bits++;
91     host_page_mask = ~(host_page_size - 1);
92 }
93
94 /* dump memory mappings */
95 void page_dump(FILE *f)
96 {
97     unsigned long start, end;
98     int i, j, prot, prot1;
99     PageDesc *p;
100
101     fprintf(f, "%-8s %-8s %-8s %s\n",
102             "start", "end", "size", "prot");
103     start = -1;
104     end = -1;
105     prot = 0;
106     for(i = 0; i <= L1_SIZE; i++) {
107         if (i < L1_SIZE)
108             p = l1_map[i];
109         else
110             p = NULL;
111         for(j = 0;j < L2_SIZE; j++) {
112             if (!p)
113                 prot1 = 0;
114             else
115                 prot1 = p[j].flags;
116             if (prot1 != prot) {
117                 end = (i << (32 - L1_BITS)) | (j << TARGET_PAGE_BITS);
118                 if (start != -1) {
119                     fprintf(f, "%08lx-%08lx %08lx %c%c%c\n",
120                             start, end, end - start, 
121                             prot & PAGE_READ ? 'r' : '-',
122                             prot & PAGE_WRITE ? 'w' : '-',
123                             prot & PAGE_EXEC ? 'x' : '-');
124                 }
125                 if (prot1 != 0)
126                     start = end;
127                 else
128                     start = -1;
129                 prot = prot1;
130             }
131             if (!p)
132                 break;
133         }
134     }
135 }
136
137 static inline PageDesc *page_find_alloc(unsigned int index)
138 {
139     PageDesc **lp, *p;
140
141     lp = &l1_map[index >> L2_BITS];
142     p = *lp;
143     if (!p) {
144         /* allocate if not found */
145         p = malloc(sizeof(PageDesc) * L2_SIZE);
146         memset(p, 0, sizeof(PageDesc) * L2_SIZE);
147         *lp = p;
148     }
149     return p + (index & (L2_SIZE - 1));
150 }
151
152 static inline PageDesc *page_find(unsigned int index)
153 {
154     PageDesc *p;
155
156     p = l1_map[index >> L2_BITS];
157     if (!p)
158         return 0;
159     return p + (index & (L2_SIZE - 1));
160 }
161
162 int page_get_flags(unsigned long address)
163 {
164     PageDesc *p;
165
166     p = page_find(address >> TARGET_PAGE_BITS);
167     if (!p)
168         return 0;
169     return p->flags;
170 }
171
172 /* modify the flags of a page and invalidate the code if
173    necessary. The flag PAGE_WRITE_ORG is positionned automatically
174    depending on PAGE_WRITE */
175 void page_set_flags(unsigned long start, unsigned long end, int flags)
176 {
177     PageDesc *p;
178     unsigned long addr;
179
180     start = start & TARGET_PAGE_MASK;
181     end = TARGET_PAGE_ALIGN(end);
182     if (flags & PAGE_WRITE)
183         flags |= PAGE_WRITE_ORG;
184     spin_lock(&tb_lock);
185     for(addr = start; addr < end; addr += TARGET_PAGE_SIZE) {
186         p = page_find_alloc(addr >> TARGET_PAGE_BITS);
187         /* if the write protection is set, then we invalidate the code
188            inside */
189         if (!(p->flags & PAGE_WRITE) && 
190             (flags & PAGE_WRITE) &&
191             p->first_tb) {
192             tb_invalidate_page(addr);
193         }
194         p->flags = flags;
195     }
196     spin_unlock(&tb_lock);
197 }
198
199 void cpu_exec_init(void)
200 {
201     if (!code_gen_ptr) {
202         code_gen_ptr = code_gen_buffer;
203         page_init();
204     }
205 }
206
207 /* set to NULL all the 'first_tb' fields in all PageDescs */
208 static void page_flush_tb(void)
209 {
210     int i, j;
211     PageDesc *p;
212
213     for(i = 0; i < L1_SIZE; i++) {
214         p = l1_map[i];
215         if (p) {
216             for(j = 0; j < L2_SIZE; j++)
217                 p[j].first_tb = NULL;
218         }
219     }
220 }
221
222 /* flush all the translation blocks */
223 /* XXX: tb_flush is currently not thread safe */
224 void tb_flush(void)
225 {
226     int i;
227 #ifdef DEBUG_FLUSH
228     printf("qemu: flush code_size=%d nb_tbs=%d avg_tb_size=%d\n", 
229            code_gen_ptr - code_gen_buffer, 
230            nb_tbs, 
231            (code_gen_ptr - code_gen_buffer) / nb_tbs);
232 #endif
233     nb_tbs = 0;
234     for(i = 0;i < CODE_GEN_HASH_SIZE; i++)
235         tb_hash[i] = NULL;
236     page_flush_tb();
237     code_gen_ptr = code_gen_buffer;
238     /* XXX: flush processor icache at this point if cache flush is
239        expensive */
240 }
241
242 #ifdef DEBUG_TB_CHECK
243
244 static void tb_invalidate_check(unsigned long address)
245 {
246     TranslationBlock *tb;
247     int i;
248     address &= TARGET_PAGE_MASK;
249     for(i = 0;i < CODE_GEN_HASH_SIZE; i++) {
250         for(tb = tb_hash[i]; tb != NULL; tb = tb->hash_next) {
251             if (!(address + TARGET_PAGE_SIZE <= tb->pc ||
252                   address >= tb->pc + tb->size)) {
253                 printf("ERROR invalidate: address=%08lx PC=%08lx size=%04x\n",
254                        address, tb->pc, tb->size);
255             }
256         }
257     }
258 }
259
260 /* verify that all the pages have correct rights for code */
261 static void tb_page_check(void)
262 {
263     TranslationBlock *tb;
264     int i, flags1, flags2;
265     
266     for(i = 0;i < CODE_GEN_HASH_SIZE; i++) {
267         for(tb = tb_hash[i]; tb != NULL; tb = tb->hash_next) {
268             flags1 = page_get_flags(tb->pc);
269             flags2 = page_get_flags(tb->pc + tb->size - 1);
270             if ((flags1 & PAGE_WRITE) || (flags2 & PAGE_WRITE)) {
271                 printf("ERROR page flags: PC=%08lx size=%04x f1=%x f2=%x\n",
272                        tb->pc, tb->size, flags1, flags2);
273             }
274         }
275     }
276 }
277
278 void tb_jmp_check(TranslationBlock *tb)
279 {
280     TranslationBlock *tb1;
281     unsigned int n1;
282
283     /* suppress any remaining jumps to this TB */
284     tb1 = tb->jmp_first;
285     for(;;) {
286         n1 = (long)tb1 & 3;
287         tb1 = (TranslationBlock *)((long)tb1 & ~3);
288         if (n1 == 2)
289             break;
290         tb1 = tb1->jmp_next[n1];
291     }
292     /* check end of list */
293     if (tb1 != tb) {
294         printf("ERROR: jmp_list from 0x%08lx\n", (long)tb);
295     }
296 }
297
298 #endif
299
300 /* invalidate one TB */
301 static inline void tb_remove(TranslationBlock **ptb, TranslationBlock *tb,
302                              int next_offset)
303 {
304     TranslationBlock *tb1;
305     for(;;) {
306         tb1 = *ptb;
307         if (tb1 == tb) {
308             *ptb = *(TranslationBlock **)((char *)tb1 + next_offset);
309             break;
310         }
311         ptb = (TranslationBlock **)((char *)tb1 + next_offset);
312     }
313 }
314
315 static inline void tb_jmp_remove(TranslationBlock *tb, int n)
316 {
317     TranslationBlock *tb1, **ptb;
318     unsigned int n1;
319
320     ptb = &tb->jmp_next[n];
321     tb1 = *ptb;
322     if (tb1) {
323         /* find tb(n) in circular list */
324         for(;;) {
325             tb1 = *ptb;
326             n1 = (long)tb1 & 3;
327             tb1 = (TranslationBlock *)((long)tb1 & ~3);
328             if (n1 == n && tb1 == tb)
329                 break;
330             if (n1 == 2) {
331                 ptb = &tb1->jmp_first;
332             } else {
333                 ptb = &tb1->jmp_next[n1];
334             }
335         }
336         /* now we can suppress tb(n) from the list */
337         *ptb = tb->jmp_next[n];
338
339         tb->jmp_next[n] = NULL;
340     }
341 }
342
343 /* reset the jump entry 'n' of a TB so that it is not chained to
344    another TB */
345 static inline void tb_reset_jump(TranslationBlock *tb, int n)
346 {
347     tb_set_jmp_target(tb, n, (unsigned long)(tb->tc_ptr + tb->tb_next_offset[n]));
348 }
349
350 static inline void tb_invalidate(TranslationBlock *tb, int parity)
351 {
352     PageDesc *p;
353     unsigned int page_index1, page_index2;
354     unsigned int h, n1;
355     TranslationBlock *tb1, *tb2;
356     
357     /* remove the TB from the hash list */
358     h = tb_hash_func(tb->pc);
359     tb_remove(&tb_hash[h], tb, 
360               offsetof(TranslationBlock, hash_next));
361     /* remove the TB from the page list */
362     page_index1 = tb->pc >> TARGET_PAGE_BITS;
363     if ((page_index1 & 1) == parity) {
364         p = page_find(page_index1);
365         tb_remove(&p->first_tb, tb, 
366                   offsetof(TranslationBlock, page_next[page_index1 & 1]));
367     }
368     page_index2 = (tb->pc + tb->size - 1) >> TARGET_PAGE_BITS;
369     if ((page_index2 & 1) == parity) {
370         p = page_find(page_index2);
371         tb_remove(&p->first_tb, tb, 
372                   offsetof(TranslationBlock, page_next[page_index2 & 1]));
373     }
374
375     /* suppress this TB from the two jump lists */
376     tb_jmp_remove(tb, 0);
377     tb_jmp_remove(tb, 1);
378
379     /* suppress any remaining jumps to this TB */
380     tb1 = tb->jmp_first;
381     for(;;) {
382         n1 = (long)tb1 & 3;
383         if (n1 == 2)
384             break;
385         tb1 = (TranslationBlock *)((long)tb1 & ~3);
386         tb2 = tb1->jmp_next[n1];
387         tb_reset_jump(tb1, n1);
388         tb1->jmp_next[n1] = NULL;
389         tb1 = tb2;
390     }
391     tb->jmp_first = (TranslationBlock *)((long)tb | 2); /* fail safe */
392 }
393
394 /* invalidate all TBs which intersect with the target page starting at addr */
395 static void tb_invalidate_page(unsigned long address)
396 {
397     TranslationBlock *tb_next, *tb;
398     unsigned int page_index;
399     int parity1, parity2;
400     PageDesc *p;
401 #ifdef DEBUG_TB_INVALIDATE
402     printf("tb_invalidate_page: %lx\n", address);
403 #endif
404
405     page_index = address >> TARGET_PAGE_BITS;
406     p = page_find(page_index);
407     if (!p)
408         return;
409     tb = p->first_tb;
410     parity1 = page_index & 1;
411     parity2 = parity1 ^ 1;
412     while (tb != NULL) {
413         tb_next = tb->page_next[parity1];
414         tb_invalidate(tb, parity2);
415         tb = tb_next;
416     }
417     p->first_tb = NULL;
418 }
419
420 /* add the tb in the target page and protect it if necessary */
421 static inline void tb_alloc_page(TranslationBlock *tb, unsigned int page_index)
422 {
423     PageDesc *p;
424     unsigned long host_start, host_end, addr, page_addr;
425     int prot;
426
427     p = page_find_alloc(page_index);
428     tb->page_next[page_index & 1] = p->first_tb;
429     p->first_tb = tb;
430     if (p->flags & PAGE_WRITE) {
431         /* force the host page as non writable (writes will have a
432            page fault + mprotect overhead) */
433         page_addr = (page_index << TARGET_PAGE_BITS);
434         host_start = page_addr & host_page_mask;
435         host_end = host_start + host_page_size;
436         prot = 0;
437         for(addr = host_start; addr < host_end; addr += TARGET_PAGE_SIZE)
438             prot |= page_get_flags(addr);
439         mprotect((void *)host_start, host_page_size, 
440                  (prot & PAGE_BITS) & ~PAGE_WRITE);
441 #ifdef DEBUG_TB_INVALIDATE
442         printf("protecting code page: 0x%08lx\n", 
443                host_start);
444 #endif
445         p->flags &= ~PAGE_WRITE;
446 #ifdef DEBUG_TB_CHECK
447         tb_page_check();
448 #endif
449     }
450 }
451
452 /* Allocate a new translation block. Flush the translation buffer if
453    too many translation blocks or too much generated code. */
454 TranslationBlock *tb_alloc(unsigned long pc)
455 {
456     TranslationBlock *tb;
457
458     if (nb_tbs >= CODE_GEN_MAX_BLOCKS || 
459         (code_gen_ptr - code_gen_buffer) >= CODE_GEN_BUFFER_MAX_SIZE)
460         return NULL;
461     tb = &tbs[nb_tbs++];
462     tb->pc = pc;
463     return tb;
464 }
465
466 /* link the tb with the other TBs */
467 void tb_link(TranslationBlock *tb)
468 {
469     unsigned int page_index1, page_index2;
470
471     /* add in the page list */
472     page_index1 = tb->pc >> TARGET_PAGE_BITS;
473     tb_alloc_page(tb, page_index1);
474     page_index2 = (tb->pc + tb->size - 1) >> TARGET_PAGE_BITS;
475     if (page_index2 != page_index1) {
476         tb_alloc_page(tb, page_index2);
477     }
478     tb->jmp_first = (TranslationBlock *)((long)tb | 2);
479     tb->jmp_next[0] = NULL;
480     tb->jmp_next[1] = NULL;
481
482     /* init original jump addresses */
483     if (tb->tb_next_offset[0] != 0xffff)
484         tb_reset_jump(tb, 0);
485     if (tb->tb_next_offset[1] != 0xffff)
486         tb_reset_jump(tb, 1);
487 }
488
489 /* called from signal handler: invalidate the code and unprotect the
490    page. Return TRUE if the fault was succesfully handled. */
491 int page_unprotect(unsigned long address)
492 {
493     unsigned int page_index, prot, pindex;
494     PageDesc *p, *p1;
495     unsigned long host_start, host_end, addr;
496
497     host_start = address & host_page_mask;
498     page_index = host_start >> TARGET_PAGE_BITS;
499     p1 = page_find(page_index);
500     if (!p1)
501         return 0;
502     host_end = host_start + host_page_size;
503     p = p1;
504     prot = 0;
505     for(addr = host_start;addr < host_end; addr += TARGET_PAGE_SIZE) {
506         prot |= p->flags;
507         p++;
508     }
509     /* if the page was really writable, then we change its
510        protection back to writable */
511     if (prot & PAGE_WRITE_ORG) {
512         mprotect((void *)host_start, host_page_size, 
513                  (prot & PAGE_BITS) | PAGE_WRITE);
514         pindex = (address - host_start) >> TARGET_PAGE_BITS;
515         p1[pindex].flags |= PAGE_WRITE;
516         /* and since the content will be modified, we must invalidate
517            the corresponding translated code. */
518         tb_invalidate_page(address);
519 #ifdef DEBUG_TB_CHECK
520         tb_invalidate_check(address);
521 #endif
522         return 1;
523     } else {
524         return 0;
525     }
526 }
527
528 /* call this function when system calls directly modify a memory area */
529 void page_unprotect_range(uint8_t *data, unsigned long data_size)
530 {
531     unsigned long start, end, addr;
532
533     start = (unsigned long)data;
534     end = start + data_size;
535     start &= TARGET_PAGE_MASK;
536     end = TARGET_PAGE_ALIGN(end);
537     for(addr = start; addr < end; addr += TARGET_PAGE_SIZE) {
538         page_unprotect(addr);
539     }
540 }
541
542 /* find the TB 'tb' such that tb[0].tc_ptr <= tc_ptr <
543    tb[1].tc_ptr. Return NULL if not found */
544 TranslationBlock *tb_find_pc(unsigned long tc_ptr)
545 {
546     int m_min, m_max, m;
547     unsigned long v;
548     TranslationBlock *tb;
549
550     if (nb_tbs <= 0)
551         return NULL;
552     if (tc_ptr < (unsigned long)code_gen_buffer ||
553         tc_ptr >= (unsigned long)code_gen_ptr)
554         return NULL;
555     /* binary search (cf Knuth) */
556     m_min = 0;
557     m_max = nb_tbs - 1;
558     while (m_min <= m_max) {
559         m = (m_min + m_max) >> 1;
560         tb = &tbs[m];
561         v = (unsigned long)tb->tc_ptr;
562         if (v == tc_ptr)
563             return tb;
564         else if (tc_ptr < v) {
565             m_max = m - 1;
566         } else {
567             m_min = m + 1;
568         }
569     } 
570     return &tbs[m_max];
571 }
572
573 static void tb_reset_jump_recursive(TranslationBlock *tb);
574
575 static inline void tb_reset_jump_recursive2(TranslationBlock *tb, int n)
576 {
577     TranslationBlock *tb1, *tb_next, **ptb;
578     unsigned int n1;
579
580     tb1 = tb->jmp_next[n];
581     if (tb1 != NULL) {
582         /* find head of list */
583         for(;;) {
584             n1 = (long)tb1 & 3;
585             tb1 = (TranslationBlock *)((long)tb1 & ~3);
586             if (n1 == 2)
587                 break;
588             tb1 = tb1->jmp_next[n1];
589         }
590         /* we are now sure now that tb jumps to tb1 */
591         tb_next = tb1;
592
593         /* remove tb from the jmp_first list */
594         ptb = &tb_next->jmp_first;
595         for(;;) {
596             tb1 = *ptb;
597             n1 = (long)tb1 & 3;
598             tb1 = (TranslationBlock *)((long)tb1 & ~3);
599             if (n1 == n && tb1 == tb)
600                 break;
601             ptb = &tb1->jmp_next[n1];
602         }
603         *ptb = tb->jmp_next[n];
604         tb->jmp_next[n] = NULL;
605         
606         /* suppress the jump to next tb in generated code */
607         tb_reset_jump(tb, n);
608
609         /* suppress jumps in the tb on which we could have jump */
610         tb_reset_jump_recursive(tb_next);
611     }
612 }
613
614 static void tb_reset_jump_recursive(TranslationBlock *tb)
615 {
616     tb_reset_jump_recursive2(tb, 0);
617     tb_reset_jump_recursive2(tb, 1);
618 }
619
620 /* mask must never be zero */
621 void cpu_interrupt(CPUState *env, int mask)
622 {
623     TranslationBlock *tb;
624     
625     env->interrupt_request |= mask;
626     /* if the cpu is currently executing code, we must unlink it and
627        all the potentially executing TB */
628     tb = env->current_tb;
629     if (tb) {
630         tb_reset_jump_recursive(tb);
631     }
632 }
633
634
635 void cpu_abort(CPUState *env, const char *fmt, ...)
636 {
637     va_list ap;
638
639     va_start(ap, fmt);
640     fprintf(stderr, "qemu: fatal: ");
641     vfprintf(stderr, fmt, ap);
642     fprintf(stderr, "\n");
643 #ifdef TARGET_I386
644     cpu_x86_dump_state(env, stderr, X86_DUMP_FPU | X86_DUMP_CCOP);
645 #endif
646     va_end(ap);
647     abort();
648 }
649
650 #ifdef TARGET_I386
651 /* unmap all maped pages and flush all associated code */
652 void page_unmap(void)
653 {
654     PageDesc *p, *pmap;
655     unsigned long addr;
656     int i, j, ret, j1;
657
658     for(i = 0; i < L1_SIZE; i++) {
659         pmap = l1_map[i];
660         if (pmap) {
661             p = pmap;
662             for(j = 0;j < L2_SIZE;) {
663                 if (p->flags & PAGE_VALID) {
664                     addr = (i << (32 - L1_BITS)) | (j << TARGET_PAGE_BITS);
665                     /* we try to find a range to make less syscalls */
666                     j1 = j;
667                     p++;
668                     j++;
669                     while (j < L2_SIZE && (p->flags & PAGE_VALID)) {
670                         p++;
671                         j++;
672                     }
673                     ret = munmap((void *)addr, (j - j1) << TARGET_PAGE_BITS);
674                     if (ret != 0) {
675                         fprintf(stderr, "Could not unmap page 0x%08lx\n", addr);
676                         exit(1);
677                     }
678                 } else {
679                     p++;
680                     j++;
681                 }
682             }
683             free(pmap);
684             l1_map[i] = NULL;
685         }
686     }
687     tb_flush();
688 }
689 #endif