メモリ領域に実行権限をつける(Linux x86)

JITコンパイラ実装のために、メモリに機械語を展開して実行させる。
メモリに機械語を配置するだけではなく、OSの機能を使って実行権限をつける必要がある。
Linuxでは、mprotectというシステムコールを使う。
C言語からmprotectを使うには、sys/mman.hをincludeする。

機械語はわからなかったので、以下のアセンブラアセンブルしてobjdump -dした。

global main
section .text
main:
    mov eax, 28
    ret

objdumpの結果。

>> objdump -d a.o                                                                                           
a.o:     file format elf32-i386


Disassembly of section .text:

00000000 <main>:
   0:   b8 1c 00 00 00          mov    $0x1c,%eax
   5:   c3             


メモリに実行権限をつけて実行させるテスト

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

#include<sys/mman.h>
#include<unistd.h>


void run(){
    unsigned char *code;
    int code_length = 64;
    
    if (posix_memalign((void**)&code,sysconf(_SC_PAGESIZE),sizeof(char) * code_length)){
        fprintf(stderr,"ERROR MEMALIGN\n");
        exit(1);
    }
    if (mprotect((void*)code,sizeof(char) * 32,PROT_READ | PROT_WRITE | PROT_EXEC)){
       fprintf(stderr,"ERROR MEMPROTECT \n");
        exit(1);
    }
    
    //MOV EAX, 28
    code[0] = 0xb8; code[1] = 0x1c; code[2] = 0x00; code[3] = 0x00; code[4] = 0x00;
    
    //RET
    code[5] = 0xc3;

    int res = ((int(*)(void))(code))();
    printf("%d\n",res);
}


int main(void){
    run();
    return 0;
}

カーソルキーが使えなくなったのでXmodmapでなんとかする。

キーボードのカーソルキーが断線により動かなくなったので、Xmodmapを使って スペースキーの横あたりにあるいらないキー+hjklで補おうとした。

hjklと同時に押してみて一番良かったのが変換キーなので、こいつに犠牲になってもらう。

keycode 100 = Mode_switch

(Mode_switchは、第二のShiftキー的なイメージ。)

あとは、変換キーを押したときのhjklの設定を書くだけ。

keycode 43 = h H Left Left
keycode 44 = j J Down Down
keycode 45 = k K Up Up
keycode 46 = l L Right Right

(=の右側は、左から、そのまま押した時、Shift、Mode_switch、Mode_switch+Shiftの順に設定する)
以上、解決。

Schemeのequal?の実装について調べたメモ

R7RSでは、equal?に循環オブジェクトを入力した場合でも必ず終了することが要求されていて、その実装方針について調べていた。
探している答えそのものな内容の論文が見つかった。
“Efficient Nondestructive Equality Checking for Trees and Graphs"という論文でunifon-findを使って循環オブジェクトを効率的に処理しようというものだった。

以下すごく雑なメモ
1、2章、読んでない
3章、pairやvectorを比較するとき、それらをunion-findを用いて、同じ集合にまとめて、次に同じ比較をするときや、不要な比較のケースをはぶいてしまおうという内容。
4章、サイズが小さく、循環構造を含まないものを比較するときに、union-findの部分が足をひっぱるので、union-findなしでk回比較して、終わらなかったらunion-findを使おうという内容
5章、4章の方針の場合、サイズが大きいものを比較する場合、結局union-findの分遅くなるので、各頂点ごとにunion-findありのものとなしのものを併用していくという内容。
6章、4章と5章を融合させるという内容。つまり、5章の方針の前にunion-findなしでk回比較させるという内容。

ELFヘッダのe_identについて調べました。

ELFはメジャーなオブジェクトファイルのフォーマット。
今回は、そのELFファイルの最初の16バイトであるe_identについて調べる。
e_identは、ELFヘッダの一部なので、readelf -hで確認することができる。

$readelf -h a.out                                                                                                                                                                                   0 < 02:49:50
ELF ヘッダ:
  マジック:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  クラス:                            ELF64
  データ:                            2 の補数、リトルエンディアン
  バージョン:                        1 (current)
  OS/ABI:                            UNIX - System V
  ABI バージョン:                    0
  型:                                DYN (共有オブジェクトファイル)
  マシン:                            Advanced Micro Devices X86-64
  バージョン:                        0x1
  エントリポイントアドレス:               0x570
  プログラムの開始ヘッダ:          64 (バイト)
  セクションヘッダ始点:          6560 (バイト)
  フラグ:                            0x0
  このヘッダのサイズ:                64 (バイト)
  プログラムヘッダサイズ:            56 (バイト)
  プログラムヘッダ数:                9
  セクションヘッダ:                  64 (バイト)
  セクションヘッダサイズ:            29
  セクションヘッダ文字列表索引:      28



中身が分かったので、ひとつづつ確認していく。
頭から16バイトをとりだす。

 $od -An -tx1 -N16 a.out                                                                                                                                                         
 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00



最初の4バイト(7f 45 4c 46)はマジックナンバー
0x7f ‘E’ ‘L’ ‘F'となっているね。

次の1バイト(02)は32bitか64bitかの区別。
/usr/include/elf.hによると02なので64-bit object。

#define ELFCLASSNONE  0    /* Invalid class */
#define ELFCLASS32  1    /* 32-bit objects */                                                                                                                                                                      
#define ELFCLASS64  2    /* 64-bit objects */
#define ELFCLASSNUM  3



次の1バイト(01)は、エンディアン
同様に確認すると、2の補数、little endianとなっている。

#define ELFDATANONE  0    /* Invalid data encoding */
#define ELFDATA2LSB  1    /* 2's complement, little endian */
#define ELFDATA2MSB  2    /* 2's complement, big endian */                                                                                                                                                         
#define ELFDATANUM  3



次の1バイト(01)はバージョン。
必ず1になっていなくてはいけないっぽい

#define EV_NONE    0    /* Invalid ELF version */
#define EV_CURRENT  1    /* Current version */                                                                                                                                                                     
#define EV_NUM    2



次の1バイト(00)は、ABI。
ABIについては、ちゃんと理解してないのだけどWikipediaでも見ればいいかな。
後回し。
00なので、ABIがSYSVであることは分かった。

#define ELFOSABI_NONE    0  /* UNIX System V ABI */
#define ELFOSABI_SYSV    0  /* Alias.  */
#define ELFOSABI_HPUX    1  /* HP-UX */
#define ELFOSABI_NETBSD    2  /* NetBSD.  */
#define ELFOSABI_GNU    3  /* Object uses GNU ELF extensions.  */
#define ELFOSABI_LINUX    ELFOSABI_GNU /* Compatibility alias.  */
#define ELFOSABI_SOLARIS  6  /* Sun Solaris.  */
#define ELFOSABI_AIX    7  /* IBM AIX.  */
#define ELFOSABI_IRIX    8  /* SGI Irix.  */
#define ELFOSABI_FREEBSD  9  /* FreeBSD.  */
#define ELFOSABI_TRU64    10  /* Compaq TRU64 UNIX.  */
#define ELFOSABI_MODESTO  11  /* Novell Modesto.  */
#define ELFOSABI_OPENBSD  12  /* OpenBSD.  */
#define ELFOSABI_ARM_AEABI  64  /* ARM EABI */
#define ELFOSABI_ARM    97  /* ARM */
#define ELFOSABI_STANDALONE  255  /* Standalone (embedded) application */

のこりの8バイトは、ABIバージョンと予約で開けられている。
ABIバージョンの形式は、ABI依存。

pycのマジックナンバーについて調べました。

Pythonバイトコードのpycの最初の4バイトにはマジックナンバーがあって、どのバージョンで作成されたのか分かるようになっている。 各バージョンのマジックナンバー
Lib/importlib/_bootstrap_external.pyを見れば分かる。 マジックナンバーは、各バージョンごとに用意されている2バイトの数値+168627479になっている。

pycからバージョンを調べる

まず、中身をみる。

$ od -tx1 a.pyc                                                  
0000000 17 0d 0d 0a b2 cb 3e 59 1f 00 00 00 e3 00 00 00
0000020 00 00 00 00 00 00 00 00 00 02 00 00 00 40 00 00
0000040 00 73 10 00 00 00 64 00 00 64 01 00 84 00 00 5a
0000060 00 00 64 02 00 53 29 03 63 02 00 00 00 00 00 00
0000100 00 02 00 00 00 02 00 00 00 43 00 00 00 73 08 00
0000120 00 00 7c 00 00 7c 01 00 17 53 29 01 4e a9 00 29
0000140 02 da 01 61 da 01 62 72 01 00 00 00 72 01 00 00
0000160 00 fa 04 61 2e 70 79 da 03 66 6f 6f 01 00 00 00
0000200 73 02 00 00 00 00 01 72 05 00 00 00 4e 29 01 72
0000220 05 00 00 00 72 01 00 00 00 72 01 00 00 00 72 01
0000240 00 00 00 72 04 00 00 00 da 08 3c 6d 6f 64 75 6c
0000260 65 3e 01 00 00 00 73 00 00 00 00
0000273

最初の4バイトは,17 0d 0d 0aなので、

>>> 23 + 13 * (1<<8) + 13 * (1<<16) + 10 * (1<<24)
168627479

マジックナンバーは168627479で、下2バイトをとりだす。

>>>168627479 & int("FFFF",16)
3351

あとは、一覧を眺めて同じやつを見つける。

#     Python 3.5b1  3330 (PEP 448: Additional Unpacking Generalizations)
#     Python 3.5b2  3340 (fix dictionary display evaluation order #11205)
#     Python 3.5b2  3350 (add GET_YIELD_FROM_ITER opcode #24400)
#     Python 3.5.2  3351 (fix BUILD_MAP_UNPACK_WITH_CALL opcode #27286)
#     Python 3.6a0  3360 (add FORMAT_VALUE opcode #25483
#     Python 3.6a0  3361 (lineno delta of code.co_lnotab becomes signed)
#     Python 3.6a1  3370 (16 bit wordcode)
#     Python 3.6a1  3371 (add BUILD_CONST_KEY_MAP opcode #27140)
#     Python 3.6a1  3372 (MAKE_FUNCTION simplification, remove MAKE_CLOSURE
#                         #27095)
#     Python 3.6b1  3373 (add BUILD_STRING opcode #27078)
#     Python 3.6b1  3375 (add SETUP_ANNOTATIONS and STORE_ANNOTATION opcodes
#                         #27985)
#     Python 3.6b1  3376 (simplify CALL_FUNCTIONs & BUILD_MAP_UNPACK_WITH_CALL)
#     Python 3.6b1  3377 (set __class__ cell from type.__new__ #23722)
#     Python 3.6b2  3378 (add BUILD_TUPLE_UNPACK_WITH_CALL #28257)
#     Python 3.6rc1 3379 (more thorough __class__ validation #23722)
#     Python 3.7a0  3390 (add LOAD_METHOD and CALL_METHOD opcodes)

バージョン3.5.2だね。

処理系からマジックナンバーを調べる

>>> import importlib.util
>>> importlib.util.MAGIC_NUMBER
b'\x17\r\r\n'
>>> int.from_bytes(importlib.util.MAGIC_NUMBER,"little")
168627479

glutで画像を表示したぞ。

ppm形式(raw)の画像を用意して、それをglutで表示する。
座標とかはやってない。
高さx幅xRGBのサイズのarrayを用意して、画像を読み込み、glDrawPixelsを実行するだけ。

コンパイル方法。(オプションが多いね。)

gcc a.c -lglut -lGL

コード

#include<GL/glut.h>
#include<stdio.h>
#include<stdlib.h>

unsigned char image[400][640][3];

int ppm_read(char *filename, unsigned char *pimage){
  FILE *fp;
  if((fp=fopen(filename,"rb"))==NULL){
     printf("ERROR:%s\n",filename);
     exit(-1);
  }
  fscanf(fp,"P6\n640 480\n255\n");
  fread(pimage,sizeof(char),640*400*3,fp);
  fclose(fp);
  return 0;
}


void disp(){
    glClear(GL_COLOR_BUFFER_BIT);
    glDrawPixels(640, 400, GL_RGB, GL_UNSIGNED_BYTE, &image[0][0][0]); 
    glFlush();
}

void resize(){

}

void keyboard(unsigned char key,int x,int y){

}

void mouse(int button,int state,int x,int y){

}

void motion(int x,int y){
    
}


void init(){
    glClearColor(0.0, 0.0, 1.0, 1.0);
    ppm_read("a.ppm",&image[0][0][0]);
}

int main(int argc,char *argv[]){
    glutInit(&argc,argv);
    glutCreateWindow("TITLE NAME");
    glutInitDisplayMode(GLUT_RGBA);
 
    glutDisplayFunc(disp);
    glutKeyboardFunc(keyboard);
    glutReshapeFunc(resize);
    glutMouseFunc(mouse);
    glutMotionFunc(motion);
 
    init();
    glutMainLoop();
    return 0;
}

syntax-rulesの同じ深さの<ellipsis>

同じ深さので、違う場所で宣言された場合どうなるのか確認した。
多くの処理系では、短いほうが優先される。

(define-syntax foo
  (syntax-rules ()
    ((_ ((a ...) ...) (( b ... ) ... ))
     (quote ( ((a b) ...) ... )))))

(display 
  (foo ((a b)(c d e)) ((A B)(C D E))));(((a A) (b B)) ((c C) (d D) (e E)))

(newline)

(display
  (foo ((a b) ( c d )) ((A B)(C D E )) ));(((a A) (b B)) ((c C) (d D)))
(newline)