My Diary (2nd)

Vixby를 관심있게 보고 있는데, facebook에 다음과 같은 event가 떴다.

Galaxy Home Mini Beta Program.

신청했다. 과연 써볼 수 있을까?

갤럭시 s7 edge가 손에 들어왔다. 액정이 금이 간채로.

한두개면 그냥 쓸텐데, 좀 많이 생겼다.

A/S 센터에서 수리하면 19만원정도

사설 수리 센터에 가도 10만원정도 예상되는데

중고가격이 그 이하다. 그래서, 수리하기로 했다.

검색하면 액정 접착제라는 것이 보인다.

광고하는 내용을 보고, 몇몇 blog를 보면 신통방통하다.

하.지.만. 그 접착제라는 것이 꽤 비싸고 (2~3만),

말하는 것과 달리 자세히 보면 제한적인 제품이다.

유리에 실금 몇개인 경우, 그나마 고려할만한 제품이다.

좀 더 찾아보니 UV 경화제.라는 것을 기본으로 뭔가 양념을 친 것같다.

그래서, 알리에서 UV 경화제 2500번을 주문했다.

그리고, 습관적으로 강화유리를 주문했다. 수리한 다음에 붙이려고 산 것인데, 이게 행운이었다.

UV 경화제, 도착후 보이는 것처럼 금위에 방울방울 떨군 다음 햇빛에 노출시켰다. 그리고, 실패했다.

나는 UV 경화제가 굳으면 일반 접착제처럼 단단하게, 유리 비슷한 강도를 보여줄 것으로 예상했는데,

그게 아니었다. 고무나 실리콘같은 경도가 나온다. 그러니까 나중에 플라스틱 카드로 긁어낼 수 있었던거다.

좀 더 검색해보니 강화유리를 UV 경화제로 붙이는 방법이 보였고,

그대로 했다. 먼저 해본 경험으로 말하자면 UV 경화제는 충분히 뿌릴 것.

강화유리로 꾹 누르면 흘러내릴 정도로. 그래야 공기기포로 고생하지 않는다.

본인은 적게 써서 몇몇 공기 기포는 빼내지 못했다.

화면을 끄고, 비스듬히 보면 내부 유리가 깨진 듯한 모양을 보여준다. 오른쪽 아래부분에 충격을 받아서 금이 쫙 갔다. 화면에 불이 들어보고 평소 사용시에는 조금 눈에 띄는 정도.

비용은

- 1.06 USD  5ml UV Glue Tp-2500 Loca

- 1.93 USD  강화유리

약 5000원정도 수리비가 들었다.

ubuntu 18.04를 판올림한 다음에 이것저것 service가 안되는 것이 몇몇 있어서

그때그때 마다 해결하면서 쓰고 있다.

linux desktop에 samba를 설정해놓고, 회사 노트북에서 이를 당겨 쓰고 있다. 아래와 같이

    Z: drive of windows 7 notebook == /home/tolkien/tmp of linux desktop

작업환경이 linux desktop이다보니 자료던 뭐던 linux desktop에서 찾고 보게 되고,

windows 7 notebook은 email, 또는 m$ office를 이용해서 출력할 때만 쓰게 된다.

(누군 libre office를 써서 linux desktop에서 출력까지 하던데.)

여하튼 이렇게 연결해놓고 쓰고 있었는데, 갑자기 접속이 안되는 것이다.

탐색기로 보면 뭔가 요란하게 나오는데, 결론은 username 하고 password가 틀리다는거다.

응? 그래서, 내가 기억하고 있는 id/passwd가 틀렸나보다 생각하고,

linux desktop에서 smbclient를 써서 확인해보면 잘 접속이 된다.

    smbclient -L <linux desktop IP> -U tolkien

혹시나해서 MacBook에서 같은 실험. 잘 접속이 된다.

이건 windows 7이 뭔가 바뀌었다는 얘기. 회사 notebook이다보니 이런저런 이유로 설정이 바뀌어져 있는 경우가 있다.

googling해서 cmd.exe에서 test를 해봤다.

    c:\Users\john> net use L: \\myserver\myshare /u:myuser mypassword

    System error 86 - The specified network password is not correct.

System error 86? 좀 더 확인해보니까, security policy를 바꾸어보라고 한다.

    c:\Users\john> secpol.msc
    #   -> Local Policies
    #    -> Network Security : LAN Manager Authentification level
    #       change it to 'Send NTLMv2 response only. Refuse LM & NTLM'

그런데, 회사에서 설정바꿀 수 없게 lock을 걸었다!

 LAN Manager Authentification level이

 'Send LM & NTLM - use NTLMv2 session security if negotiated' 고정되어 있슴.

다행히 누가 댓글로 다른 해결책을 알려줬다. smb.conf 에 아래 한줄 추가

    ntlm auth = true

오늘도 이렇게 평화는 지켜졌슴.

방송통신대 강의를 듣다보니 wxMaxima라는 tool을 사용한다. Maxima라는 수식을 간단하게 풀어주거나 Graph를 그려주는 program의 wxWidget front-end. 예전에 써봤던 Mathematica의 open source version으로 추측된다. 이걸 macbook에 설치해보니 실행이 제대로 안된다. 그래서, 다른 front-end중에서 이전에 tensorflow때 써먹었던 jupyter가 있길래 여기에 붙여본다고 삽질. (기준은 mac OS X 10.13.6 High Sierra )

1. brew를 통해서 maxima를 설치한다.

brew install maxima

2.   maxima를 실행한 다음에 다음 명령어가 먹으면, jupyter 설치(6번)로 들어간다.

f(x) := sin(x);

3. maxima 동작이 이상하면 이제 source build를 해야 한다. 먼저 sbcl이라는 lisp interpreter를 설치해야 한다.

brew install sbcl

4. 그리고, maxima source를 받아서 build. (mac은 platypus라는 것이 필요하다.)

git clone https://github.com/andrejv/maxima.git

brew install platypus

cd maxima

./bootstrap

make -f macosx/Makefile

5. 그러면 ~/Desktop/Maxima.app 이라는 directory가 생긴다. app을 실행할 것이 아니므로 적당한 곳은 옮기고, 그 안에 있는 실행 shell script을 실행가능한 path로 link 걸어놓는다. maxima를 실행시켜서 잘 동작하는 거 확인. 여기까지 안되면 그냥 windows binary 가져다가 사용할 것.

mv ~/Desktop/Maxima.app ~/Public

ln -s /Users/tolkien/Public/Maxima.app/Contents/Resources/maxima.sh ~/bin/maxima

6. jupyter를 설치해야 한다. 그리고,  ~/.sbclrc를 생성해서 다음과 같은 내용을 추가해주자.

brew install python3 pip3

pip3 install jupyter

MacBook-Air:work tolkien$ cat ~/.sbclrc 

(setf sb-impl::*default-external-format* :utf-8)

7. quicklisp이라는 것도 설치.

curl -O https://beta.quicklisp.org/quicklisp.lisp

sbcl --load quicklisp.lisp

- 여기부터는 lisp intepreter 명령임 -

(quicklisp-quickstart:install)

(ql:system-apropos "vecto")

(ql:quickload "vecto")

(ql:add-to-init-file)

(quit)

8. maxim-jupyter source를 download.

git clone https://github.com/robert-dodier/maxima-jupyter.git

cd maxima-jupyter

mkdir -p binary/binary-sbcl

maxima

- 여기부터 maxima 명령임 -

:lisp (load "load-maxima-jupyter.lisp")

:lisp (sb-ext:save-lisp-and-die #P"binary/binary-sbcl/maxima-jupyter-exec" :executable t :toplevel 'maxima-jupyter:kernel-start-exec)

10. 중간에 아래와 같은 message를 내면서 build 실패하면, lisp file을 patch해야 한다.

; /Users/tolkien/.cache/common-lisp/sbcl-1.4.16-macosx-x64/Users/tolkien/quicklisp/dists/quicklisp/software/pzmq-20171019-git/grovel__grovel /Users/tolkien/.cache/common-lisp/sbcl-1.4.16-macosx-x64/Users/tolkien/quicklisp/dists/quicklisp/software/pzmq-20171019-git/grovel__grovel.grovel-tmp.lisp

While evaluating the form starting at line 19, column 0

  of Maxima encountered a Lisp error:

 Couldn't execute "/Users/tolkien/.cache/common-lisp/sbcl-1.4.16-macosx-x64/Users/tolkien/quicklisp/dists/quicklisp/software/pzmq-20171019-git/grovel__grovel": Permission denied

Automatically continuing.

To enable the Lisp debugger set *debugger-hook* to nil.

#P"/Users/tolkien/work/maxima-jupyter/./load-maxima-jupyter.lisp":; 

10.1 patch file.

--- /Users/john/tmp/grovel.lisp 2019-02-23 03:45:12.000000000 +0900

+++ /Users/john/quicklisp//dists/quicklisp/software/cffi_0.20.0/grovel/grovel.lisp 2019-02-23 03:45:04.000000000 +0900

@@ -243,6 +243,7 @@

             (link-executable exe-file (list o-file)))

         (error (e)

           (grovel-error "~a" e)))

+      (apply 'invoke `(#+bsd ,@`("chmod" "755" ,exe-file)))

       (invoke exe-file lisp-file)

       lisp-file)))

11. 무사히 build가 끝나면 다음과 같은 실행파일을 볼 수 있을 것이다. (이제 다 왔다!)

MacBook-Air:maxima-jupyter tolkien$ ls -lh binary/binary-sbcl/

total 196736

-rwxr-xr-x  1 tolkien  staff    84M  2 23 03:46 maxima-jupyter-exec*

12. 이제 jupyter에 maxim kernel을 추가.

python3 ./install-maxima-jupyter.py --exec=`pwd`/binary/binary-sbcl/maxima-jupyter-exec

또는, virtualenv 환경에서 jupyter를 실행한다면 아래처럼 설치위치를 지정해주어야 한다.

python3 ./install-maxima-jupyter.py --prefix=/Users/tolkien/tf --exec=`pwd`/binary/binary-sbcl/maxima-jupyter-exec

13. jupyter를 실행하고, New button을 눌러서 maxima kernel이 있는 것을 확인하면 된다.

jupyter-notebook

참고 site:

• http://maxima.sourceforge.net - maxima official site
• http://maxima-online.org  - maxima web front-end
• https://github.com/andrejv/maxima - maxima GitHub mirror
• https://github.com/robert-dodier/maxima-jupyter - maxima-jupyter Github
• https://www.quicklisp.org/beta/ - quicklisp official site

맥북이 두대가 있는데, 그중 macbook 2008은 지원되는 OS가 mac OS 10.7.5 Lion까지다. 이유는 CPU는 64bit이지만, EFI Bios가 32bit라서... google로 찾아보면 어찌어찌 hack해서 이후 OS를 설치하는 덕후들도 있지만, 솔직히 그냥 평범한 notebook에 hackintosh 설치하는 것과 크게 다를게 없다.

그동안 별 불만없이 2nd PC로 잘 쓰고 있었다. 헌데 open source software 진영에서도 하나둘씩 지원을 멈추더니 google chrome, firefox가 EOL (End Of Life)를 선언하고 이후 web browsing하는 데, 하나둘씩 불편함이 늘어나고 있다. 최근에 문제가 된 것은 SSL 인증 문제. 느린 것을 참겠지만, 아예 접속이 안되니... 아직까지 firefox 마지막 지원 version (48.0.2)으로 internet을 쓸 수 있겠지만, 이것도 언제까지 갈지..

결정적으로 그동안 잘 써왔던, brew에서 10.7.5에 대한 지원을 다음 version부터 하지 않겠다고 하면서 편하게 쓰던 3rd party software도 힘든 상황이 되었다. 그 대안으로 쓸 수 있는 것이 아직까지 지원하고 있는 MacPort와 TigerBrew.

여기서 TigerBrew가 brew의 fork라서 쓰기 편한데, 이건 말그대로 Tiger OS, 즉, PowerPC Mac을 지원하는 project라는 거다. bottle도 전부 ppc binary라서 내가 쓸 때는 항상 build부터 시작한다. 가끔 build error는 덤.

google을 뒤져봐도 macOS 10.7.5를 Apple 지원없이 계속 쓰지 위한 움직임은 보이지 않는다. 68k Mac이나 PPC Mac처럼 사용기간이 오래된 것도 아니고, 충성스런 사용자층이 있는 것도 아닌 것같고. 실사용기와 레트로 사이에 낀 어중간함이 꽤 지속될 것같다.

macbook 2008에 mac OS 10.7.5를 설치해서 web browser 좀 써보겠다고 낑낑대다가 이럴바에는 linux가 났겠다고 다시 linux를 설치했다. 내가 써놓은 글을 보니 엄두가 안 나서, 다른 방법으로 시도.

CD/DVD drive가 망가졌으므로 bootable USB를 만들어야 하는데, 많은 site가 mac OS 10.7.5에서 동작하지 않는 program를 쓰라고 한다. 하지만, 난 command line friendly이므로...

1. ubuntu 16.04.5 LTS (64bit) iso image를 받는다.

2. mac OS에서 hdiutil를 써서 image 변환.

hdiutil convert -format UDRW -o ~/path/to/target.img ~/path/to/ubuntu.iso

3. dd로 image를 USB memory에 write (용량 2G이상이면 됨.) 대개, disk0는 macbook HDD이므로, USB memory는 /dev/disk1 이다. 잘 모르겠으면, df 또는 disk list 명령으로 찾아보자.

sudo dd if=~/path/to/target.img.dmg of=/dev/disk1 bs=1m

그리고, "Option" key를 누르고 전원을 켜면, USB memory를 선택하고 booting할 수 있다. 상당히 오래 걸리므로 인내.인내.인내 (한 10분정도 있어야 설치화면을 볼 수 있었던 것 같다.)

설치가 다 끝나면, network이 ethernet device만 되고, WiFi가 되지 않는다. linux console에서 lspci 로 보면 Broadcomm 4321 chip이 보이고, 이건 kernel에서 지원된다고 되어 있는데, iwconfig 로 보면 보이지 않는다. modprobe -a b43 으로 kernel module을 load하면 firmware가 없다고 투덜대면서 module load에 실패하는 것을 볼 수 있다. 집 network은 이미 WiFi만 제공하므로 어떻게든 잡아야 한다. (이전 설치에서는 ubuntu 12.04 설치 -> upgrade로 이 문제를 풀었다.)

4. bcmwl-kernel-source 제거

apt-get purge bcmwl-kernel-source

5. 설치 usb에서 b43-fwcutter 찾아서 설치

dpkg -i b43-fwcutter_019-2_amd64.deb

6. broadcom legacy driver binary download후 b43-fwcutter로 firmware 추출

tar jxf broadcom-wl-5.100.138.tar.bz2

b43-fwcutter -w /lib/firmware broadcom-wl-5.100.138/linux/wl_apsta.o

7. reboot

이후, usb mouse 사용중에 touch pad를 disable하거나, keyboard typing중에 touchpad를 disable하는 trick 도 찾아서 써봤는데...

.

.

.

.

.

.

.

booting하는데, 한 5분정도 걸리는 걸보고 내가 뭐한건가... 읖조린 다음

backup해두었던 mac OS 10.7.5로 돌아갔다.

참고 site:

 - How to Create a Bootable Ubuntu USB Drive, for Mac, in OS X

 - How to Enable Wi-Fi on MacBook, Mac Mini, MacBook Air for Ubuntu/Linux OS

 - 파일들.

broadcom-wl-5.100.138-wl_apsta.only.tar.bz2

disable_tpad_while_typing.py

README.fix

작년에 MacBook 2008을 쓰면서 이것저것 막히기 시작했다.

chrome도 막히고, firefox도 out-dated. brew 조차도 안되는 상황.

그래서, 쓰던 HDD는 빼고 (잘했지...), 새 SSD에 linux를 깔았다. 그리고, 몇번 끄적거리다보니 다른 notebook에 밀리기 시작함. 생각해보면, Linux를 쓰는데, 2008년식 물건을 쓸 이유가 없다. 주위에 좀 찾아보면 2011년 PC notebook에 깔아도 MacBook 2008보다 빠르니까...

어제 자다가 갑자기 MacBook이 생각나서 이리저리 생각하다가 다시 Mac OS로 돌아가기로 결심했다. 주위에 8 Bit MSX나 68k Mac을 취미로 쓰는 사람들을 생각해보니, MacBook은 그것보다 더 현역이다. internet도 되고, firefox도 source 구해다가 설치하면 될 것같고, 레트로 취미로 나쁘지 않다는 생각이 들었다.

일어나서 쑤셔넣었던 HDD (무려 250GB다!)로 갈아끼우니, 반가운 화면이 떴다.

그리고, firefox를 source build하려다보니 다음과 같은 error가 brew에서 나왔다.

curl: (35) error:1407742E:SSL routines:SSL23_GET_SERVER_HELLO:tlsv1 alert protocol version

아차... 이것때문에 linux 깔았었지. 누군가 이 문제를 풀었을 것이라고 생각해서 googling해서 찾아낸 link - https://try.gitea.io/donbright/lm

저기에서 repository를 tarball로 받아서 설치하면 curl, git, ssl을 쓸만한 version으로 wrapping된다.

tar xf ~/Downloads/lm-master.tar.gz
export PATH=$HOME/lm/bin:$PATH
# put that export line in your ~/.profile for now... you can remove if u need later)
cd lm
./buildy.sh

이제 firefox를 다시 build 시도할 예정.

참고로, MacBook에 binary들이 얼마나 중첩이 되어 있나하면.

sel-yjoh-m1:~ tolkien$ /usr/bin/git --version
git version 1.7.12.4 (Apple Git-37)
sel-yjoh-m1:~ tolkien$ /usr/local/bin/git --version
git version 2.13.3
sel-yjoh-m1:~ tolkien$ ~/lm/bin/git --version
git version 2.17.0

~/lm/bin을 뺄 수 있는 방법도 찾아야 할 것같다.

참고문헌:

- Installing Homebrew on a old Lion mac

- Tigerbrew - A little experimental fork of Homebrew that adds support for PowerPC Macs, and Macs running Tiger (or Leopard)

가지고 있는 macbook 2008 early model은 64bit cpu이지만, 32bit EFI BIOS여서 mac OS update에서 버림받았다. 그래도 그럭저럭 쓰다가 이젠... 사파리, 크롬도 못 쓰고, firefox 32bit 간신히 사용중인 상태에서 얼마전부터 ssh로 접속 안되는 곳이 생기기 시작. 아마 openssl issue로 추정. 그외 다수...라는 핑계로 mac OS 버리고 linux로 이주 결정.

가지고 있는 mac book 사양:

 - macbook 2008 + 2.5G RAM

 - DVD/CD ROM이 뭔가 읽어본지 꽤 되었고, 멀쩡한 음악CD를 읽지 못하는 것으로 보아 못씀.

 - mac OS 10.7.5

어쨌든 내 macbook은 안된다. 일단, boot media로 인식하지 못한다. rufus, unetbootin등 다 해봤지만, 어쨌든 usb로 booting하는데 실패했다. 그러다가, custom efi binary를 써서 booting하는 방법을 따라해보니 된다. 이에 전산고고학을 전공하시는 후학을 위해서 간략하게 기록해본다.

boot-linux-from-usb-flash-drive-on-macbook의 본문에 있는 내용보다 댓글 마지막에 제공하는 link가 더 잘 되는 것같다. (linux 환경에서 하는 것을 추천한다. 닭이던 달걀이던)

1. usb memory disk에 GPT partition을 만든다. sdX는 sda, sdb, ...

  dd if=/dev/zero of=/dev/sdX bs=10M 으로 깨끗하게 밀어버리고 하는 것을 추천한다.

  gdisk로 GPT partition으로 disk map을 쓴다고 선언하고 (use blank GPT),

  partition 하나를 만든다. type은 0700 (Microsoft Basic Data)

2. mkfs.vfat -F 32 /dev/sdX1 로 포맷

3. mkdir -p /mnt/1; mount /dev/sdX1 /mnt/1 으로 mount한 다음

   mkdir -p /mnt/1/elf/boot 로 directory 생성

4. /mnt/1/elf/boot directory에 파일 복사.

   -

   - boot.iso는 linux 설치배포 iso image

   최종적으로 usb memory에 다음처럼 있으면 된다.

그후, option key를 눌러서 boot media을 EFIboot로 선택하면 booting 된다. 안되면 다른 글을 찾아볼 것. 여기서 커피 한잔. 이제 시작한 거다.

설치는 다른 얘기다.
1. 배포폰 + 32/64bit 조합만으로 많은 삽질이 있었다.
2. 일반 pc처럼 mac OS -> grub로 얌전하게 booting되지 않는다.
   -> rEFInd라는 emulator를 설치해주어야 한다.
3. 나는 겪지 않았지만, 주변장치관련 잡다한 작업이 필요할 수 있다고 한다.

일반 PC와 달리 rEFInd를 설치할 partition이 필요하다. ubuntu 설치 usb로 booting후 바로 설치로 들어가는 것이 아니라 terminal을 열고 partition을 만들고 파일을 복사해주어야 한다.

- 설치할 disk가 sdb라고 한다면

- gdisk /dev/sdb 해서 GPT partition map을 쓴다고 선택한 다음

   100M size의 partition을 만든다. type은 ef00 (EFI system)

- mkfs.vfat -F32 /dev/sdb1 으로 format 후 mount

  mkdir -p /boot/temp-efi

  mount /dev/sdb1 /boot/temp-efi

- rEFInd 를 설치한다.

# mkdir ~/rEFInd/ && cd ~/rEFInd/
# wget http://downloads.sourceforge.net/project/refind/0.7.7/refind-bin-0.7.7.zip
# unzip refind-bin-0.7.7.zip
# cd refind-bin-0.7.7/
# ./install.sh

 잘 설치되었으면, 다음으로 마무리

# cd /boot/temp-efi # Or wherever you mounted your UEFI partition
# mv EFI/refind/ EFI/boot/ # Rename the directory
# mv EFI/boot/refind_ia32.efi EFI/boot/boot.efi # Rename the file

그리고, ubuntu 설치로 들어가서 설치하는데, 설치할 disk 선택시 전부 쓰기를 선택하면 만들었던 rEFInd partition이 날라간다. 따라서, 설치할 partition을 수동으로 만들어주어야 한다.

그외...

나는 ubuntu 12.04.5 64bit desktop을 먼저 설치한 다음, 14.04 -> 16.04로 단계적으로 upgrade했다.

- Fedora Live는 boot 초반에 grub console로 떨어진다. 뭔가 문제가 있겠지.

- ubuntu 16.04 desktop 32/64bit 둘 다 설치후반 grub 설치에서 error 나오고 멈춤.

참고 site :

 1. boot-linux-from-usb-flash-drive-on-macbook

 2. 136 - UEFI-boot directly from Ubuntu-based ISO files

 3. Linux-only installation on a 2006 Macbook using rEFInd

https://lwn.net/Articles/175432/

커널은 유용한 데이터 구조를 구현하기위한 많은 라이브러리 루틴을 포함합니다. 그중 두 가지 유형의 tree가 있습니다 : radix tree와 red-black tree. 이 기사에서는 radix tree API를 살펴볼 것입니다. red-black tree는 나중에.

Wikipedia는radix tree 항목을 가지고 있지만 Linux radix tree는 잘 설명되어 있지 않습니다. Linux radix tree는 (포인터) 값이 (긴) 정수 키와 연관 될 수있는 메커니즘입니다. 그것은 저장면에서 상당히 효율적이며, 조회에서 꽤 빠릅니다. 또한 Linux 커널의 radix tree에는 특정 항목과 태그를 연결하는 기능을 비롯하여 커널 관련 요구 사항에 따라 일부 기능이 있습니다.

위쪽 치즈 다이어그램은 Linux radix tree의 leaf node를 보여줍니다. 노드는 다수의 슬롯을 포함하며, 각각의 슬롯은 트리 작성자가 관심을 갖는 포인터를 포함 할 수 있습니다. 빈 슬롯은 NULL 포인터를 포함합니다. 이 tree들은 상당히 넓습니다 - 2.6.16-rc 커널에서는 각 radix tree node에 64 개의 슬롯이 있습니다. 슬롯은 (긴) 정수 키의 일부로 인덱싱됩니다. 가장 높은 키 값이 64보다 작으면 전체 트리를 단일 노드로 나타낼 수 있습니다. 그러나 일반적으로 키의 다소 큰 세트가 사용됩니다. 그렇지 않으면 간단한 배열을 사용할 수 있습니다. 그래서 더 큰 tree는 다음과 같이 보일 것입니다 :

이 tree는 3 level deep입니다. 커널이 특정 키를 검색 할 때 루트 노드에서 적절한 슬롯을 찾기 위해 가장 중요한 6 비트가 사용됩니다. 다음 6 비트는 중간 노드의 슬롯을 인덱싱하고, 최하위 6 비트는 실제 값을 가리키는 포인터를 포함하는 슬롯을 나타냅니다. 자식이 없는 노드는 트리에 존재하지 않으므로 radix tree가 성긴(sparse) tree에 대한 효율적인 저장소를 제공 할 수 있습니다.

Radix tree는 메인 라인 커널 트리에 몇 명의 사용자가 있습니다. PowerPC 아키텍처는 트리를 사용하여 실제 IRQ 번호와 가상 IRQ 번호를 매핑합니다. NFS 코드는 관련 아이 노드 구조에 트리를 첨부하여 미해결 요청을 추적합니다. 그러나 radix tree의 가장 널리 사용되는 것은 메모리 관리 코드에 있습니다. 백업 저장소를 추적하는 데 사용되는 address_space 구조에는 해당 매핑과 연결된 코어 페이지를 추적하는 radix tree가 있습니다. 무엇보다도 이 트리를 사용하면 메모리 관리 코드가 더럽거나 쓰기 저장중인 페이지를 빠르게 찾을 수 있습니다.

커널 데이터 구조에서 일반적인 것처럼 기수를 선언하고 초기화하는 두 가지 모드가 있습니다.

  #include <linux/radix-tree.h>

   RADIX_TREE(name, gfp_mask);  /* Declare and initialize */

   struct radix_tree_root my_tree;
   INIT_RADIX_TREE(my_tree, gfp_mask);

첫번째 형식은 지정된 이름으로 radix tree를 선언하고 초기화합니다. 두번째 형식은 런타임에 초기화를 수행합니다. 두 경우 모두 메모리 할당이 수행되는 방법을 코드에 알려주기 위해 gfp_mask 를 제공해야합니다. radix tree 연산 (특히 삽입)이 원자적 컨텍스트에서 수행되는 경우, 주어진 마스크는 GFP_ATOMIC 이어야합니다.

  int radix_tree_insert(struct radix_tree_root *tree, unsigned long key,
                         void *item);
   void *radix_tree_delete(struct radix_tree_root *tree, unsigned long key);

Radix tree에 항목을 넣지 못하는 것이 심각한 문제가 될 수있는 상황이 있습니다. 이러한 상황을 피하기 위해 한 쌍의 특수 기능이 제공됩니다.

  int radix_tree_preload(gfp_t gfp_mask);
   void radix_tree_preload_end(void);

  void *radix_tree_lookup(struct radix_tree_root *tree, unsigned long key);
   void **radix_tree_lookup_slot(struct radix_tree_root *tree, unsigned long key);
   unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                       void **results,
                    unsigned long first_index,
                    unsigned int max_items);

마지막으로, radix_tree_gang_lookup ()을 호출하면 first_index 에서 시작하는 키 값이 오름차순으로 결과의 max_items 항목까지 반환됩니다. 돌려 주어지는 아이템의 수는 요구한 것보다 적을 수 있습니다만, 짧은 반환 (제로 이외)은 트리에 값이 없는 것을 의미하지 않습니다.

radix tree 함수는 내부적으로 어떤 종류의 잠금(locking)도 수행하지 않는다는 것을 알아야합니다. 여러 스레드가 트리를 손상시키거나 다른 종류의 불쾌한 경쟁 조건에 빠지지 않도록 하는 것은 호출자의 몫입니다. Nick Piggin은 현재 free 트리 노드를 읽기 위해 copy-update를 사용하는 패치를 배포하고 있습니다. 이 패치는 (1) 결과 포인터가 원자적 컨텍스트에서만 사용되며 (2) 호출 코드가 자체 경쟁 조건 생성을 피하는 한 잠금없이 조회 작업을 수행 할 수 있습니다. 그러나 패치가 병합 될 예정인지 명확하지 않습니다.

radix tree 코드는 "태그"라는 기능을 지원합니다. 특정 비트가 트리의 항목에 설정 될 수 있습니다. 태그는 예를 들어 더럽거나(dirty) 쓰기 저장 상태(under write back)인 메모리 페이지를 표시하는 데 사용됩니다. 태그 작업을 위한 API는 다음과 같습니다.

  void *radix_tree_tag_set(struct radix_tree_root *tree,
            unsigned long key, int tag);
   void *radix_tree_tag_clear(struct radix_tree_root *tree,
            unsigned long key, int tag);
   int radix_tree_tag_get(struct radix_tree_root *tree,
            unsigned long key, int tag);

태그는 radix_tree_tag_clear () 로 제거 할 수 있습니다; 다시 한번 얘기하자면, 반환 값은 태그(또는 untag)가 붙은 항목에 대한 포인터입니다. radix_tree_tag_get () 함수는 키에 의해 색인된 항목이 주어진 태그 세트를 가지고 있는지를 검사 할 것이다. key 가 없으면 반환 값은 0이고, key 가 있지만 태그가 설정되어 있지 않으면 -1, 그렇지 않으면 +1입니다. 그러나, 이 기능은 현재 소스 코드에서 주석으로 처리되어 있으므로 트리 코드에서는 이를 사용하지 않습니다.

태그를 쿼리하는 데는 두 가지 다른 기능이 있습니다.

  int radix_tree_tagged(struct radix_tree_root *tree, int tag);
   unsigned int radix_tree_gang_lookup_tag(struct radix_tree_root *tree,
                                           void **results,
                       unsigned long first_index,
                       unsigned int max_items,
                       int tag);

결론적으로, radix tree API의 또 다른 흥미로운 점은 radix tree를 파기 ​​할 수있는 기능이 없다는 것입니다. 분명히 radix tree가 영원히 지속될 것이라고 가정합니다. 실제로는, radix tree에서 모든 항목을 삭제하면 루트 노드 이외의 모든 메모리가 해제되어 정상적으로 처리 될 수 있습니다.

또 다른 radix tree 설명

• http://jake.dothome.co.kr/radix-tree/

• http://timewizhan.tistory.com/entry/%EB%9D%BC%EB%94%95%EC%8A%A4-%ED%8A%B8%EB%A6%ACRadix-Tree

https://lwn.net/Articles/256368/

When asked which of the changes in 2.6.24 was most likely to create problems, an informed observer might well point at the i386/x86_64 merger. As it happens, that large patch set has gone in with relatively few hitches, but a rather smaller change has created quite a bit of fallout. The change in question is the updated API for the management of scatterlists, which are used in scatter/gather I/O. This work broke a number of in-tree drivers, so it seems likely to affect a lot of out-of-tree code as well.

Scatter / gather I/O는 시스템이 실제 메모리에 분산되어있는 버퍼에 대해 DMA I / O 작업을 수행 할 수있게합니다. 예를 들어, 사용자 공간에서 생성 된 대형 (다중 페이지) 버퍼의 경우를 생각해보십시오. 응용 프로그램은 연속적인 범위의 가상 주소를 보지만 그 주소 뒤에 있는 물리적 페이지는 거의 서로 인접하지 않습니다. 단일 I / O 작업에서 해당 버퍼를 장치에 기록하려면 다음 두 가지 중 하나를 수행해야합니다. (1) 데이터를 물리적으로 인접한 버퍼에 복사해야하거나 (2) 장치가 물리적 주소 및 길이 목록을 사용하여 각 세그먼트에서 올바른 양의 데이터를 가져옵니다. Scatter / gatter I/O는, 연속적인 버퍼로 데이터를 복사 할 필요를 제거함으로써,  I/O 작업의 효율성을 크게 높일 수있을뿐만 아니라 물리적으로 연속적인 대형 버퍼의 생성이 처음에는 문제가 될 수 있다는 문제를 해결할 수 있습니다.

커널 내에서, scatter / gather DMA 연산에 사용될 버퍼는 <linux / scatterlist.h>에 정의 된 하나 이상의 scatterlist 구조의 배열로 표현됩니다. 이 배열은 전통적으로 단일 페이지 내에 들어가도록 제한되어있어 분산 / 수집 작업에 최대 길이를 부여합니다. 이 한계는 하이 엔드 시스템에서 병목 현상이되는 것으로 나타났습니다. 그렇지 않으면 대용량 버퍼 (일반적으로 디스크 장치간에)를 전송할 때 이점이 있습니다. 결과적으로 그 한계를 극복 할 수있는 방안이 모색되고 있습니다. 간혹 mailing list에 나타나는 대용량 블록 크기 패치가 한 가지 방법입니다. 그러나 커널을 2.6.24 커널로 만들었던 해법은 Scatter / gatter list의 길이를 묶어서(chained) 제거하는 것입니다.

Chained Scatter / gatter list는 둘 이상의 페이지로 구성 될 수 있으며 해당 페이지도 실제 메모리에 흩어질 수 있습니다. 이 체인(chaining)이 완료되면 버퍼 포인터의 하위 비트 두 개를 사용하여 체인 항목과 목록의 끝을 표시합니다. 이 사용법은 드라이버 코드에서 걱정할 필요가 있는 것이 아니지만 특수 bit와 체인 pointer가 있으면 드라이버가 scatter list에서 작동하는 방식을 일부 변경해야합니다.

연결(chaining)을 수행하지 않는 드라이버는 일반적으로 kcalloc () 또는 일부 호출을 통해 scatterlist array를 일반적인 방식으로 할당합니다. 2.6.23 이전에는 초기화 단계가 필요하지 않았으며, 아마도 전체 배열을 초기화하지 않았습니다. 그러나 그것은 바뀌었습니다. 드라이버는 다음과 같이 scatterlist array를 초기화해야합니다:

   void sg_init_table(struct scatterlist *sg, unsigned int nents);

  void sg_set_page(struct scatterlist *sg, struct page *page,
            unsigned int len, unsigned int offset);

   void sg_set_buf(struct scatterlist *sg, const void *buf,
                unsigned int buflen);

   void sg_mark_end(struct scatterlist *sg, unsigned int nents);

여기서 nents 는 scatterlist의 유효한 항목 수입니다.

   struct scatterlist *sg_next(struct scatterlist *sg);

    int i;
   struct scatterlist *list, *sgentry;

   /* Fill in list and pass it to dma_map_sg().  Then... */
   for_each_sg(i, list, sgentry, nentries) {
    program_hw(device, sg_dma_address(sgentry), sg_dma_len(sgentry));
   }

chaining feature를 이용하려는 드라이버는 조금만 더 작업해야합니다. scatterlist의 각 조각은 독립적으로 할당되어야하며 그 조각은 다음과 함께 체인(chained)되어야합니다.

   void sg_chain(struct scatterlist *prv, unsigned int prv_nents,
         struct scatterlist *next);