이항계수 증명(pascal's rule)과 프로그래밍

이항계수 식은 다음과 같다

<<증명>>
좌변을 풀어쓰면 다음과 같다.


분모를 합쳐서 정리하면, 짜잔!

증명 끝.

이항계수를 프로그램 하면 다음과 같다.

int bino(int n, int r) {
  if (r == 0 || n == r)) return 1;
  return bino(n-1, r-1) + bino(n-1, r);
}

물론 메모이제이션을 하는 것이 효과적이다.

aptitude

ubuntu는 sw 관리가 windows 처럼 편하게 되어 있다.
데비안 계열은 가장 보편적으로 dpkg / apt-get을 이용하는데
나는 언젠가부터 aptitude를 사용하고 있다.
aptitude를 이용하면 SW 간에 dependency 오류를 자동으로 감지해주고 고쳐주기 때문에 사용했는데 다음utility들도 활용할 수 있다.

• aptitude-curses: TUI로 보여줌
• aptitude-create-state-bundle: 현재 aptitude 상태를 저장
• aptitude-run-state-bundle: 복구

아주 편하다.

C main design

일반적으로 bootup code는 startup.S로 작성한다.
startup.S에는 다음 내용이 들어간다.
- vector table
- stack pointer 초기화
- 전역변수 초기화
- 기타 이미지 로딩
- pc를 main으로 이동, 꼭 main이 아니어도 되며, startup.S에서 branch 해주기만 하면 된다. 이 때 부터 C 코드를 사용 가능함.
- C code를 사용하려면 기본적으로 변수 초기화, sp 초기화 등을 해야 한다. 하지 않으면 당연히 data abort!

변수의 class
- register variable
- 예약어는 register이며, 쓴다고 항상 적용되지 않고, 성능에 영향을 준다고 판단하면 그냥 stack에 저장한다.
- 단, register를 사용하면, 주소값을 읽을 수 없다. 원래 register에 저장하라고 하는 것이니깐.
- local variable
- auto 예약어인데 일반적으로 생략된다.
- static variable
- global variable

memory layout
- 아래서부터,
- TEXT(program code)
- RODATA(constant)
- DATA(initialized data)
- BSS(uninitialized data)
- HEAP(BSS 이후로 커감)
- STACK(메모리 끝에서 부터 내려옴)
- 원하는 section에 넣으려면, linker를 이용한다.
- t32에서 section 확인하려면, sYmbol.List.SECtion

Inline assembly
- C보다 빠른 처리를 위함이고, __volatile__ 예약어를 사용해야 컴파일러가 맘대로 최적화 하지 않는다
- 일반적인 형태:
- __asm__ __volatile__("" : "

" : "" : "")
- clobber는 개발자가 직접 register를 제어한다면 설정, compiler는 사용 못하도록 하며, 생략 가능하다.
- ex.
__asm__ __volatile__("add %0, %1, %2" : "=r" (result) : "r" (kind), "r" (embedded) : "r0", "r1")
r0, r1은 안쓴다는 의미임

Colling Convention
- ARM사에서 제시한 표준: PCS(procedure call standard), APCS(ARM procedure call standard), TPCS(Thumb ~), AAPCS(ARM Arch ~)
- r0, r1은 argument / result
- r2, r3는 argument / scratch register 등등..
- r13: stack pointer
- r14: link register

Call Assembly - C와 Assembly 상호 호출 방법
- Assembly에서 global keyword를 사용하여 선언하고 c에서 사용
- C symbol은 Assembly에서 .extern keyword 사용하여 호출
예시
startup.S
.extern main
BL main
.global MMU_DisableiCache
MMU_DisableiCache :
mrc p15,0,r0,c1,c0,0
bic r0, r0,#R1_I
mcr p15,0,r0,c1,c0,0
mov pc,lr

main.c
int main() {
MMU_DisableiCache();
return 0;
}

Call C++
- C와 Assembly처럼 심볼을 그대로 가져다 쓸 수 없음.
- compiler가 함수명을 가공하기 때문임.
- c++에서는 extern "C" { }를 이용해서 C의 symbol을 가져옴.

compile

C 파일을 compile 하면(main.c)
- 전처리기가 main.i를 생성
- compiler가 main.S를 생성
- assembler가 main.o를 생성
- 사람이 읽을 수 있는 언어를 hex code로 변경해 준다.
- objdump -S main.o <-- object의 정보를 확인할 수 있다.
- linker가 a.elf를 생성
- linker가 하는 역할은 object 파일을 메모리에 mapping을 하는 것
- input file들이 같은 메모리에 위치하여 서로 symbol을 사용할 수 있게 해준다.
- 각 object들의 .text(code), .data 들을 section별로 정리해서 elf로 저장한다.
- objcopy로 a.bin을 생성
- objcopy는 elf의 header, debug info 등을 날려버리고 binary만을 추출한다.
- 디버깅을 하려면 그래서 elf가 필요하다.
- gcc option인 --save-temps를 넣으면 위의 이미지들을 삭제하지 않는다.

booting mode

Booting mode는 어떤 메모리를 이용하는지에 따라 여러가지가 있다.
보통 Hardware pin으로 설정할 수 있도록 하며, 각 mode별로 memory mapping이 달라진다.
- NOR flash mode: NOR는 비싸고 부피가 큰 메모리로, 주소에 접근해서 실행 가능하다. 그래서 부트로더를 NOR flash에 넣고 부팅할 수 있다.
- NAND flash mode:
-NAND는 싸고 집적도가 높다. 하지만 주소가 없고 블락별로 data를 읽을 수 있도록 되어 있다. 즉 I/O port만 있어서 전자적 신호로 Page단위로 load하여 주소 접근이 가능한 다른 메모리에 복사하여 사용해야 한다.
- 일반적으로 MCU 내부에 IRAM에 복사해서 사용한다.
- 간단히 요약하자면, IROM이 NAND에서 IRAM으로 부트 코드를 복사한 다음에 PC를 IRAM으로 이동해 준다. IRAM은 DRAM을 초기화 하고 OS image를 얹은 다음 PC를 DRAM으로 이동해 주어 'stepping stone' 방식으로 부팅하게 된다.
- 일반적으로 boot code를 이동하는 IRAM 주소는 vendor datasheet에 있음.
- 그 외에 network booting mode / usb booting mode 등이 있다.

Linker script

일반적으로 복잡한 Memory map이 필요한 binary를 위해 사용 된다.
Linker가 필요한 정보
- 입력 section들이 어떻게 region으로 그룹화 되었는지 그룹화 정보
- Memory map에서 각 region이 어디에 위치한지 정보

Section name and macro
- .text: __TEXT_START__ / __TEXT_END__
- .bss: __BSS_START__ / __BSS_END__
- .data ..

Linker script를 사용하기 위한 옵션
- ld 옵션에 -T FILE 또는 --script FILE 으로 사용함.
- ex.
LDFLAGS = ~~~ -T linker.ld -Map $(OUTDIR)/$(BIN).map

Linker script 작성
- OUTPUT 형식
- OUTPUT_FORMAT("elf32-littlearm", "elf32-bigarm")
- OUTPUT_ARCH(arm)
- entry point
- ENTRY(_start)
- sections
- SECTIONS
{
section-command
section-command
..
}
- ex.

SECTIONS
{
        .text __TEXT_START__ :
        {
                __TEXT_START__ = .;
                *startup.o (.text);
                *main.o (.text);
                *(.text);
                . = ALIGN(4);
                __TEXT_END__ = .;
        }
}

작성 예시

OUTPUT_FORMAT("elf32-littlearm")
OUTPUT_ARCH(arm)

ENTRY(_start)

__TEXT_START__ = 0x20000000;

SECTIONS
{
        .text __TEXT_START__ :
        {
                __TEXT_START__ = .;
                *startup.o (.text);
                *main.o (.text);
                *(.text);
                . = ALIGN(4);
                __TEXT_END__ = .;
        }

        .rodata :
        {
                __RODATA_START__ = .;
                *startup.o (.rodata);
                *main.o (.rodata);
                *(.rodata);
                __RODATA_END__ = .;
                . = ALIGN(4);
        }
        .bss :
        {
                __BSS_START__ = .;
                *startup.o (.bss);
                *main.o (.bss);
                *(.bss);
                __BSS_END__ = .;
                . = ALIGN(4);
        }

        _end = .;
        __end = _end;
        PROVIDE(end = .);
}

man page 작성법..

linux 표준함수, 쉘 바이너리 등 terminal에서 실행하려는 것들에 대한 궁금증이 있으면,
가장 먼저 찾아보는 man page!

man page에 대해 알아보고 작성하는 방법을 정리한다.
man page를 열 때
$ man $(NUMBER) $(TARGET)
NUMBER에 해당하는 숫자는 무엇일까?
섹션 이름
1 누구나 실행할 수 있는 사용자 명령 (User Commands)
2 시스템 호출 (System Calls), 즉 커널에서 제공하는 함수
3 C 라이브러리 함수 (C Library functions)
4 디바이스와 네트워크 인터페이스 (Devices and Network Interfaces), 즉 /dev 디렉토리에 있는 특별한 파일들
5 파일 포맷 (File Formats), 예를 들어 /etc/passwd
6 게임과 데모 (Games and Demos)
7 환경, 테이블, 매크로 (Environments, Tables, and Macros) 등의 잡다한 여러 가지들
8 시스템 관리자만 실행할 수 있는 시스템 관리용 명령들 (Maintenance Commands)
9 커널 루틴에 관련된 문서들의 리눅스만의 독자적인 저장소
n 새로운 문서들의 저장소. 보다 적당한 장소로 이동된다.
o 오래된 문서들의 저장소. 유예 기간으로 보관되고 있는 것들이다.
l 특정 시스템에 대한 로컬 문서들
출처: 모름(잘 정리된 것이 있어 긁어왔는데 출처를 깜빡했다.. 원문의 작성자 분께 죄송하다는 말씀 드리며, 삭제 요청 시 삭제하도록 하겠습니다.)

본격적으로 파일은 어떻게 만드느냐...
파일명은 NUMBER에 해당하는 숫자를 확장자로 넣어야 한다.
즉, 예를 들면,

$ vi /usr/local/man/myman.1

이런 방식이다.
기본적으로 /usr/local/man과 /usr/share/man 등의 folder에 주로 넣으며, 확장하고 싶으면 $(PATH)에 넣어두면 된다.
man page를 열어보면 알겠지만 헤더도 있고 자동으로 인덴트도 되어 있는 것을 볼 수 있다.
.SH + NAME / SYNOPSIS / DESCRIPTION / OPTIONS / SEE ALSO / COPYRIGHT / AUTHOR 등 구분을 하고
.TP / .PP로 행을 구분한다.

예시는 위에 언급한 폴더에 아무거나 열어보면 된다.

merge remote git project!

다른 repository의 git project를 merge 하려면?

1. remote server의 정보를 추가
2. fetch(정보를 받아옴)
3. merge

간단하다.
.git/config를 열어보면 다음과 같이 remote server의 주소가 있다

[remote "A"]
         url = ssh://address = server/address
         projectname = project/name
         fetch = +x:x

나는 remote B의 git을 merge 할 것이다. 그러려면 remote B의 서버 주소가 필요하다.
 git remote add [-t ] [-m ] [-f] [--tags|--no-tags] [--mirror=]
<예시>

$ git remote add -t branch myname ssh://xxx

그러면, .git/config에 다음이 추가된다.
[remote "lap_8916_kk"]
         url = ssh://xxx
         fetch = +y:y

그런 뒤

$ git fetch myname

하면 fetch를 하고,

$git merge myname/branch

하면 merge가 시작된다.

참 쉽죠잉?

ubuntu eclipse에서 F2 '툴팁' 배경색 오류

'툴팁'<-- p="">

ubuntu에서 eclipse를 사용하다보면 도움말 부분이 검은색 배경으로 보이는 현상 때문에 빡침이 이만저만이 아니다.
이를 고치려면 툴팁 색을 변경하면 된다.

theme를 변경할 수 있으면 하고, 내가 사용하는 ubuntu 14.04는 theme 설정이 ambiance, radiance, high contrast 세 가지 밖에 안되게 되어 있다.
그래서 쉬운 방법으로는 gnome color chooser를 설치하면 된다.

$sudo aptitude install gnome-color-chooser




근데 문제가 있다..
gnome-color-chooser를 설치하면 이상하게도 gnome-session 자체 색이 반전되는 이상한 현상이 있다.
그래서 위의 처리를 하고 난 삭제 했다
$sudo aptitude remove gnome-color-chooser
 이상한 리눅스의 세계..<올바르지 않은 정보라 삭제함>

리눅스 커널 심층 분석 - 17장, 장치와 모듈

리눅스는 모놀리틱 커널로서 모듈 독립적이지 않고 한 개 수정하면 전체를 재 build 해야 하는 system이다.

다음은 insmod / rmmod 하는 과정이다.

pic1

insmod / rmmod는 user app인데실행시에는 ko를 user 영역에 copy를한후 kernel 영역에넣는다.

mknod: 장치 driver에 접근하기 위해서 VFS에 node 

--> /dev/SK dentry를 찾아서 inode를 만든다. 이 때는 file가 만들어지지 않았기 때문에 &def_cur_fops를 가리키고 있다. 이 때 open()을 하면, files에 비어있는 fd[3]에 객체를 만들면서 f_dentry, f_op 등을 매핑한다. 그런 후에 device reg 할 때 넣은 &SK_fops를 불러다가 open을 하게 됨!! 그 이후에는 직접 SK_open()으로 간다! 

/proc/devices에서 정보를 확인할 수 있다.

device module이란?

--> device들을 character device로 등록하자니.. 많아지니깐 관리가 힘들어짐.

--> 그래서 VFS(Virtual File System)가 만들어짐. charicter device / block device / network device를 접근할 수 있음.

--> 장치 유형은 다음과 같다.

• Blkdevs, 블록 장치 - HDD 
• Cdevs, 캐릭터 장치 - 키보드, 마우스 
• Network  devices, 네트워크 장치 - 이더넷 장치 

 

hello world device driver:

static int hello_init(void) 
{ 
pr_info("Hello world!"); 
return 0; 
} 
 
static void hello_exit(void) 
{ 
pr_info("Goodbye world!"); 
} 
 
module_init(hello_init); //시작지점 hello_init 등록 
module_exit(hello_exit); //모듈이 메모리에서 제거될 때 호출 
 
MODULE_LICENSE("GPL"); 
MODULE_AUTHOR("author"); 
MODULE_DESCRIPTION("Hello world, module"); 

모듈 만들기 - Makefile에 추가 

모듈 설치 

• 위치: /lib/module/버전/kerne/drivers/xxxx/helloworld.ko 
• # make modules_install //설치 

모듈 의존성 생성 

• # depmod -A 
• /lib/module/버전/modules.dep //모듈 의존성 정보 

모듈 적재 

• # insmod helloworld.ko //모듈을 메모리에 추가 
• # rmmod helloworld //삭제 
• # modprobe helloworld [모듈인자] //해당 모듈이 필요로 하는 다른 모듈도 설치 
• # modprobe -r helloworld //삭제 

설정 옵션 관리 - Kconfig 

모듈 인자 

• module_param(name, type, perm); //이름, 형, 권한 
• module_param_named(name, variable, type, perm); //외부 노출 이름, 내부 변수, 형, 권한 
• module_param_string(name, string, len, perm); //이름, 내부 변수(string은 문자열임), 형, 권한 
• module_param_array(name, type, nump, perm); //이름, 형, 배열에 저장할 항목 개수, 권한 
• moduel_param_array_named(name, array, type, nump, perm); 
• MODULE_PARM_DESC(): 설명 추가 
• <linux/module.h>에 위 함수에 대한 설명 있음 

노출 심볼 

• EXPORT_SYMBOL() 
• EXPORT_SYMBOL_GPL() //EXPORT_LICENSE("GPL")만  

• 장치 모델 
• <linux/kobject.h> kobjects(kernel object type) 
• <linux/kobject.h> struct kobject 
• <linux/cdev.h> struct cdev에 struct kobject가 들어가면 kobject가 제공하는 표준 함수를 쓸 수 있음. 
• Struct ktype: kobject의 기본 속성을 정의함. 소멸 동작, sysfs 동작 등 기본 동작, 쉽게는 공유 동작의 집합임. 
• Struct kset: 
• 묶여있는 kobject는 한 묶음의 기본 클래스로 동작함 
• 연관이 있는 kobject를 모아줌 
• Struct kobject * kobject_create(void); 

struct kobject *kobj;  kobj = kobject_create();  if (!kobj)  return -ENOMEM;

• • 참조 횟수 증감 
  • struct kobject *kobject_get(struct kobject *kobj); 
  • void kobject_put(struct kobject *kobj); 
  • 확인은 의 kref_get() 사용 
  • Sysfs에 추가/제거 
  • int kobject_add(struct kobject *kobj, struct kobject *parent, const char *fmt, ...); //추가 
  • void kobject_del(struct kobject *kobj); //제거 
  •  
  • /proc에 파일 만드는 법 -insmod하면 /proc에 파일을 하나 만드는거다! 
  • create_proc_entry() / remove_proc_entry() 이용하면 됨. 
  • 예제 /06.FileSystem/03.proc_my 확인할 것 
  • /sys (참고) 
  • 2.6 이전에는 /sys (systfs)가 없었음. 디바이스 모델과 함께 추가된 것이라고 생각하면 됨. 
  • /sys는 그렇지 않지만 /proc은 맘대로 만들어도 된다. 
  • /sys/class는 논리적인 장치 
  • /sys/bus에 device들이 붙어있음.
  • 덧 
  • module_init() 주소 보다 module_exit()가 낮은 주소값을 가지고 있다. 
    • 웃긴건 /proc/modules에 나오는 주소가 module_exit()와 동일한 주소를 가지고 있다. 즉 module_exit가 함수들 처음이고 이 모듈의 첫 주소랑 동일하다고 보면 된다. 
  • kernel 시작 주소는 #define TASK_SIZE 0xBF000000로 설정 가능함. 
  • application이 open()을 호출하면, 
    1. 'swi5' system call 하여 kernel mode(svc)로 변경됨. sys_open()을 호출함. 
    2. sys_open()이 inode의 file_operations의 i_rdev에서 major/minor 정보를 확인함 
    3. struct file 생성한 후 위에 로드한 file_operations를 멤버에 load함. 
    4. .open = mydrv_open()을 호출함. 
    5. 앱의 fd = open()의 open()은 mydrv_open()의 return이 아닌 sys_open()의 return 값임. 즉 file의 pointer 값임. 
  • read()를 호출하면 
    1. 바로 file_operations에 접근할 수 있음. 
  • close()를 호출하면 
    1. 'swi6' system call 하여 kernel mode(svc)로 변경 
    2. sys_close() 호출 
    3. mydrv_close() 호출 
    4. file_operations 삭제 
  • LDM에 대해서… 
    1. 목적: PnP/Power 통합관리 
    2. 내부 구조: 객체(kobj), sysfs  node 생성. 
    3. 구현 방법: (TBC) 
    4. 모든 드라이버에는 kobj를 등록해야 한다. 
    5. 윈도우의 WDM을 따라했음 
  • 장치파일/디바이스 네임/모듈 네임 
    • 장치파일: mknod 명령으로 생성, 응용프로그램이 사용 
    • 디바이스 네임: 
      • # cat /proc/devices 실행시 출력 
      • 드라이버소스에서 설정하여 커널에 등록 
    • 모듈네임: 
      • lsmod 실행시 출력 
      • 드라이버 소스 빌드시 결정 
  • /dev 폴더에 대해서.. 
  • Android는 부팅 전에는 /dev가 없다. init process 하면서 device 들을 확인하여 하나씩 넣는다. 
  • desktop은 kernel 부팅시 /dev가 만들어짐. package에서 동적으로 만들어줌.