OMAP2 processor에서 kernel의 secondary bootup

리눅스 커널을 스터디를 통해서 분석한지가 벌써 4년전인것 같다.

그떄 당시는 2.6.15버젼인가가 최신이고 2.6.13이 안정판이라 arm rearview 기반으로

2.6.13 버젼을 분석했던 기억이 난다. 

분석 초기에 개인적으로는 smp 머신에서 초기화는 1개의 cpu에서 해주고 

나머지 cpu를 어떻게 startup 해주는지가 상당히 궁금했다. 

다음은  당시에 내가 썼던 글이다. 

===============================

kernel_init  커널 쓰레드에서 다른 CPU를 다 꺠워준다. 

호출 순서는 다음과 같다.

start_kernel() -> rest_init() -> kernel_init -> smp_prepare_cpus() -> poke_milo() ( SYS_FLAGSCLR 레지스터의 

하위 2비트를 클리어) -> (pen_release = -1, realview_secondary_startup() )

후에 rearview_secondary_startup 루틴이 pen 값이 release 될때까지 루프

kernel_init -> smp_init() -> cpu_up() -> _cpu_up() -> __cpu_up() -> boot_secondary() -> pen relase

후에 realview_secondary_startup() 루틴이 secondary_startup()으로 점프하면

secondary_startup() 함수에서 나머지 cpu를 up 해준다. 

=================================

omap2에서도 크게 달라지지 않았지만 달라진 부분이 있다면 boot_secondary() 에서 

omap_modify_auxcoreboot0(0x200, 0xfffffdff);로 두번째 core의 startup을 준비하는 부분과

를 부팅한다는 점과  정도이다. 

Dalvik VM의 개괄적 Source 분석

Dalvik VM은 Android에서 돌아가는 VM이다. 이전에도 포스트 한바와 같이 

Phoneme project, harmony의 코드와도 외형과 핵심 구조체 등이 상당히 유사하다.

이전 포스트 이후 harmony를 대략적으로 분석해 보았으며 

결론은 대략 비슷한데 phoneme와 harmony는 상당히 일치하고 dalvik은 harmony를

바탕으로 만들어진 것이 맞다고 봐야 할듯하다. 

직접적인 코드 외에도 초기화시 로드하는 핵심클래스가 동일한 것들도 몇가지 있다.

예를 들면 다음과 같은 것들이 있다. ( dalvik/vm/Init.c의 dvmJniStartup()을 참고하자. )

org/apache/harmony/luni/platform/PlatformAddress.java

org/apache/harmony/luni/platform/PlatformAddressFactory.java

org/apache/harmony/nio/internal/DirectBuffer.java

간단히 dalvik vm이 실행되는 process를 정리해 보자.

main() -> option을 위한 메모리 할당 -> option 파싱 -> JNI_CreateJavaVM() -> findClass()

-> GetStaticMethodID() -> CallStaticVoidMethod() -> DetachCurrentThread() -> DestroyJavaVM() 

dalvik/vm/main.c의 main() 함수가 entry point이다. 대략 위와 같은 과정을 거치는데 거의 모든 

초기화의 과정이 JNI_CreateJavaVM()에서 이루어진다. 

이후에는 실행시킬 클래스를 findClass()로 실행시킬 main 메소드를 GetStaticMethodID()로 찾는다.

이후 CallStaticVoidMethod()로 class의 main 메소드를 실행시키면 이후의 과정은 main 메소드가

종료할때까지는 intepreter와 dex 파일과의 상호작용이라 봐야 하겠다. 

종료는 DetachCurrentThread()와 DestroyJavaVM()의 두가지 과정으로 볼수 있는데 

Exception에 의한 종료와 정상 종료 크게 두가지 경우가 있을수 있다.

jvm의 경우 일반적으로 따로 Thread를 사용하지 않아도 최소 1개의 쓰레드를 가지고 있는데 

이를 main thread라고 부른다. 일반적으로 static void main(String[] args)으로 선언한 메소드의

코드를 실행하는 역할을 한다고 보면 된다. 

dalvik vm의 전체개요를 이해하기 위해서는 JavaVM, JNIEnv의 두가지 구조체를 이해하는 것이

상당히 중요한데 코드에서는 다음과 같이 정의되어 있다. 

#if defined(__cplusplus)

typedef _JNIEnv JNIEnv;

typedef _JavaVM JavaVM;

#else

typedef const struct JNINativeInterface* JNIEnv;

typedef const struct JNIInvokeInterface* JavaVM;

#endif

C로 정의된 JNINativeInterface나 JNIInvokeInterface의 경우 디바이스 드라이버를 개발해

보신분들은 상당히 익숙한 구조일듯한 변수와 함수 포인터의 집합으로 구조체를 만들어 놓았다.

정리해 보면

JNIEnv는 대략적으로 dalvik vm의 환경 설정과 관련된 함수들이 쭈욱 모아져 있는데 

코드를 분석하기 위해서는 우선 CallMethod 계열, GetMethod 계열, FindClass 부분을 우선적으로

보는 것이 좋을 것이다.

JavaVM의 경우는 

DestroyJavaVM, AttachCurrentThread, DetachCurrentThread, GetEnv, AttachCurrentThreadAsDeamon

등의 단촐하게 5가지만 있다. 

JNIEnv와 JavaVM 구조체의 함수 포인터들은 각각

JavaVM: main -> JNI_CreateJavaVM()에서 gInvokeInterface의 값으로

JNIEnv: main()->JNI_CreateJavaVM()에서 gNativeInterface의 값으로 

셋팅된다. 

이후의 과정은 서술한 바와 같이 class를 찾고 class의 static main 메소드를 찾고 이를 호출하는

과정이다. 실제 코드는 다음과 같이 되어 있다.

(*env)->CallStaticVoidMethod(env, startClass, startMeth, strArray);

gInvokeInterface에서 찾아보아도 호출하는 함수의 실제 이름도 CallStaticVoidMethod로 동일하다.

CallStaticVoidMethod는 내부에서 CallStaticVoidMethodV를 호출하는데 이함수는 crags, scope

등으로 찾으려하면 잘 나오지 않는데 이는 코드의 선언이 다음처럼 되어 있기 떄문이다. 

 "##"은 변수 또는 함수의 이름을 접합시켜 주는 역할을 한다. 

위의 코드에서는 CallStatic##_jname##MethodA 처럼 사용됐는데 _jname이 컴파일 타임에 결정되어

반드시 결정되어 있어야만 하며 

예를 들어, CALL_STATIC(jbyte,Byte,result.b, false); 의 코드가 있다면

CallStaticByteMethodA와 같은 함수선언이 된것과 같은 효과가 있다. 

그럼 CallStaticVoidMethodV를 잠깐 살펴보자. 

JNI_ENTER()로 쓰레드의 상태를 변경해준후 바로 dvmCallMethodV()를 호출해준다. 

프레임에 공간을 확보한후에 argument를 처리하고 dvmInterpret()를 호출하여 

본격적으로 dex의 opcode의 처리를 시작한다. 

여기서 부터는 다시 복잡해 지므로 자바의 메소드 호출 방식 및 메소프 스택을 

처리하는 법에 관해서는 다음글에서 이어서 포스트한다. 

LIRe의 소개( LUCENE 기반의 image retrieval library)

Lucene Image Retrieval의 약자이다. 


이름처럼 Image에서 몇가지 descriptor를 추출한 다음

Lucene에 각 descriptor를 하나의 필드로 해서 indexing 및 retrieval하는 

자바기반의 라이브러리로 보면 된다. 


즉 CBIR (Content Based Image Retrieval)용 오픈소스이다. 

CBIR 오픈소스는 찾아봐도 많지가 않은데 뭐 이유야 여러가지가 


있겠지만 아직까지 CBIR이라는 분야가 아직 많이 알려지지 않은


점이 가장 큰듯하다.

LIRe의 소스는 http://www.semanticmetadata.net/lire/에서 받을수 있다.

현재 최신버젼은  0.8이다. Demo와 Src 버젼으로 나눌수 있는데 

Demo 버젼은 GUI쪽의 부분을 주로 포함하고 있고 Src 버젼은

기본 LIRE의 src를 포함하고 있다. 헤깔리기 쉬운 부분이 GUI의 소스 또한

Demo 버젼에 포함되어 있고 Src 버젼에는 GUI부분의 소스가 없다. 

Demo의 실행법은 간단한데 

> java -jar liredemo.jar 를 입력하면 다음과 같은 창이 뜬다. 

 GUI 작동법은 어렵지 않으니 직접해보면 된다. indexing 속도가 생각보다 느려서 

 마음에 썩 들지는 않지만 CBIR 오픈소스가 있다는 자체에 감사해야 하는 상황인지도


 모르겠다. 

 LIRe가 이미지를 인덱싱하기 위해 사용하는 Descriptor는 다음과 같고 인덱싱하는


 필드명 또한 Descriptor명을 그대로 사용한다.

( net.semantic.metadata.lire.DocumentBuilder를 참고하자)

1. Scalable Color

2. Color Layout

3. Edge Histogram

4. Color Correlogram

5. Color Histogram

6. CEDD ( Color and Edge Directivity Descriptor )

7. FCTH ( Fuzzy Color and Texture Histogram )

8. TAMURA

9. Gabor

10. SIFT

11. SIFT Histogram

 11가지의 Descriptor를 사용한다. 

 각각을 검색해보면 각 Descriptor당 한개씩 논문이 나올정도로 CBIR에서 적통적으로

 사용하는 Descriptor들이다. 

 SIFT 알고리즘 하나만 해도 직접 구현하기는 상당히 까다로운데 

 암튼 저자가 많은 노력을 기울임에는 틀림이 없다. 

 각 Descriptor의 구현은 net.semantic.metadata.lire.imageanalysis 패키지에 들어있다. 

 패키지를 보면 다음과 같을 것이다. 

 CBIR쪽에 관심이 많다면 각각의 소스를 분석해보자. 꽤 심플하게 코드를 구현하여서

 분석하기는 어렵지 않을것이다.

lucene의 MoreLikeThis를 사용한 간단한 추천 시스템 만들기

 Lucene의 contrib중 queries 폴더에 보면 MoreLikeThis와

 FuzzyLikeThisQuery등이 포함되어 있다.

 사실 추천 시스템이라 말하기 좀 민망하긴 하지만 어찌됐던

 MoreLikeThis를 이용하여 문서 추천시스템을 만드는 것도 가능하다.

 MoreLikeThis는 주어진 다큐먼트의 Term Frequency Vector를 만들고

 이를 통해서 새로운 쿼리를 만드는 기능을 한다.

 즉 인덱싱된 문서중 주어진 문서와 가장 유사한 문서를 찾을수 있도록

 만들어 준다.

 TF를 이용해 문서의 key term을 추출하는 방식은 매우 고전적인 방식이지만

 아직도 많이 쓰인다. 궁금한 분은 다음의 논문을 읽어보도록 하자.

  "Newman, M.E.J. and M. Girvan, 2004. Finding and evaluating community structure in networks. Phys. Rev. E., 69: 026113"

 Lucene In Action 1판, 2판에 모두 MoreLikeThis에 관한 내용이 포함되어

 있으니 책에 있는 코드의 핵심 부분만 간단히 살펴보자.

  IndexReader reader = IndexReader.open(directory);
  MoreLikeThis mlt = new MoreLikeThis(reader);

  ...

  for ( int docID = 0 ; docID < numDocs; docID++){
    ...
    Query query = mlt.like(docID);
   TopDocs similarDocs = searcher.search(query,10);
    ...
  }

  1. 우선 IndexReader를 인자로 주어 MoreLikeThis 객체를 생성한다.

  2. 인덱스된 전체 문서에 대해서 각 문서의 term frequency vector를
      생성하고 이를 통해 query를 만든다.

  3. 주어진 쿼리로 인덱싱된 문서에서 다시 검색을 한다.


 즉 위의 코드는 인덱스된 모든 문서에 대해서 가장 유사한 문서들을

 찾는 역할을 한다.

 MoreLikeThis 객체의 like 메소드는 overloading되어 있어서

 사실 4개의 인자를 받을수 있는데 다음과 같다.

 1. 인덱싱된 문서의 번호


 2. File 객체


 3. reader 객체


 4. url 객체

 2,3,4 번의 경우 직접 term frequency를 구하여 term frequency vector를 만들고

 1번의 경우에는 IndexReader의 getTermFreqVector() 메소드를 이용하여

 term frequency vector만든다.


 lucene 내부에서 사용하는 term frequency vector는 TermFreqVector

 인터페이스를 implements 하거나 implements한 클래스를

 상속하여 만들어진다.

 IndexReader의 종류에 따라 사용하는 TermVector 클래스가 다르므로

이는 나중에 다른 글에서 설명하겠다.


 그럼 org.apache.lucene.demo에 들어있는 SearchFiles를 약간 수정하여

 인덱스된 문서들중 주어진 URL의 문서와 가장 유사한 문서를 찾는 예제를

 간단히 만들어 보겠다.

 1. 우선 다음의 import 구문을 추가한다.

 import org.apache.lucene.search.similar.MoreLikeThis;
 import java.net.*;

 2.  Search시에 사용하는 Query 객체와 관련한 구문을 다음과 같이 수정해보자.

 MoreLikeThis mlt = new MoreLikeThis(reader);
 mlt.setMinTermFreq(2);
 mlt.setMinDocFreq(2);

 Query query = mlt.like(new URL("http://wittgena.blogspot.com/2011/07/lucene-incremental-indexing.html"));


 사용법이 매우 간단하다.

 나머지는 모두 동일하고 while(true){} 구문만 제거하면 될것이다.

 MoreLikeThis에 필드는 따로 지정해주지 않았는데 지정해주지

 않으면 "contents" 필드를 기본값으로 사용한다.

 나의 경우 위의 코드로 linux kernel의 documentation 폴더의 일부 문서를

 인덱싱한후 돌려보니 대략 15개의 문서가 검색이 된다.

 각자 코드를 수정하여 실행해보자. 코드를 첨부한다.

 다운로드


 ps. mahout을 이용하여 lucene에서 term vector를 추출하는 방법도 있다.
      이는 나중에 다른 글에서 설명하도록 하겠다.
      lucene의 TermVector 객체를 알아두면 textmining에
      lucene을 사용할수도 있고 여러모로 유용하다.

lucene에서 n-gram, shingle 사용하기

 lucene에는 n-gram tokenizer와 shingle analyzer가

( 정확히는 shingle analyzer wrapper)

 포함되어 있긴 하지만 3.0.1 버젼을 기준으로 할때 contrib쪽에 포함되어 있다.

 n-gram과 shingle을 가끔 혼동하시는 분도 계신데 둘은 약간 다르다고 볼수 있다.

 n-gram이 한 문자를 기반으로 하는 반면에 shingle은 한 단어를 기반으로 한다.


 "you can select"을 예를 들어보면,

 n-gram 방식으로 bi-gram으로 한다면 yo, ou, uc, ca, an 이 될 것이고

 shingle 방식으로 2-shingles로 한다면 you can, can select가 될 것이다.

 검색을 해보니 lucene에서 n-gram을 사용하는 법에

 관한 블로그는 이미 있는 듯하여

 나는 lucene에서 shingle을 사용하는 방식을 간단히 설명하겠다.

 lucene의 contrib쪽에 보면 analyzers 소스 폴더가 있다.

이 analyzers에 n-gram과 shingle 둘다 포함되어 있다.


 우선 "ant build-contrib" 명령어를 통해 contrib쪽을 빌드하면

 build/contrib/analyzers/common 폴더 밑에 lucene-analyzers-x.x.x-dev.jar 파일이

 생성된다. ( x는 버젼명이다. 즉, 나의 경우는 3.0.1이 된다.)

 이 jar파일을 classpath에 포함한후 src/java/org/apache/lucene/demo의 IndexFiles.java

 에서 다음의 두 부분을 수정한후 빌드해 보자.

 1. import 부분에 다음을 추가한다.
  import org.apache.lucene.analysis.shingle.*;

  2. IndexWriter 객체의 생성 부분을 다음과 같이 수정한다.

  (대략 60 ~ 70 라인 사이에 있다. )
IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR),
                                                //new StandardAnalyzer(Version.LUCENE_CURRENT),
                                                new ShingleAnalyzerWrapper(new        StandardAnalyzer(Version.LUCENE_CURRENT),3),
                                                true,
                                                IndexWriter.MaxFieldLength.LIMITED);

  IndexWriter의 생성자에서 무엇이 수정되었는지는 쉽게 알수 있을것이다.

 의미는 기본 analyzer로 StandardAnalyzer를 사용하고 shingle의 최대 크기를 3으로

 한다이다.

 이후 나머지 searcher를 이용한 검색과정등은 모두 동일하다.

Lucene의 Ranking Algorithm 변경

 lucene은 사실 그렇게 쉽지 많은 라이브러리이다.

 lucene의 ranking algorithm을 변경하는 방법은 여러가지인데  이중 가장

 기본적인것이 TF-IDF cosine similarity 공식 (또는 scoring fomula)을 변경하는

 것이다.  그 외에도 Query에서 가중치를 주거나 Searcher에서 HITS Collector의

 순서를 변경하는 방법, Document의 Field별 가중치를 다르게 주는법(boosting) 등등등

 여러가지가 있다.

 일단 scoring fomula를 수정하는 방법을 살펴보자.

( Lucene in action의 3장을 보면 이 내용이 잘 설명되어 있다.)

 우선 src/java/org/apache/lucene/search 폴더에 보면 DefaultSimilarity 클래스가 있다.

 메소드를 보면 computeNorm(), lengthNorm(), queryNorm, tf(), sloppyFreq(), idf()

 등등이 있다. 이 클래스는 IndexWriter 클래스에서 사용하는데 DefautSimilarity

 클래스를 상속해서 새로운 Similarity 클래스를 만들면 간단히 공식을

 변경할수 있다.

 물론 변경후 반드시 IndexWriter에 등록을 해주어야 한다.


 다음과 같이 DefaultSimilarity 클래스를 상속하여 새로운 클래스를 만들어보자.

import org.apache.lucene.search.*;

public class MySimilarity extends DefaultSimilarity {
public float tf(float freq){
return (float)(Math.sqrt(freq));
}

public float idf(int docFreq,int numDocs){
return (float)(Math.log(numDocs/(double)(docFreq+1))+1.0);
}

}

TF와 IDF를 계산하는 공식만 수정하는 간단한 소스이다.

 이제 IndexWriter 객체에 등록한다.



 IndexWriter writer = new IndexWriter(FSDirectory.open(index),
                                  new StandardAnalyzer(Version.LUCENE_CURRENT),              
                                  create,
                                  new IndexWriter.MaxFieldLength(1000000));
 writer.setSimilarity(new WikiSimilarity());

 당연한 얘기겠지만

 인덱싱을 하기전에 IndexWriter에 등록을 해주어야 한다.

 이제 수정된 공식으로 다큐먼트를 인덱싱하게 된다.

perl로 작성한 간단한 cosine similarity 소스

 요즘에는 python이 인기가 더 많은듯 한데 개인적으로 python을 별로

 좋아하지 않는다. 사실 매우 편협한 이유인데 들여쓰기와 함수의 시작

 과 끝이 { }로 구분되지 않는다는 점때문이다.

 간단히 Cosine similarity를 구하기 위해서 python이나 perl과 같은 스크립트

 언어로 스크립트를 짜야 할 때가 많은데 다음의 cosine similarity를 구해주는

 간단한 perl 스크립트를 이용해 보시라.


 사용법은 간단하다.

 document.txt 라는 파일을 만들고 파일에 여러 다큐먼트를 다음과 같은

 포맷으로 합친후 스크립트를 그냥 실행하면 된다.

 <TITLE> doc1 </TITLE>

 This is document1.

 <TITLE> doc2 </TITLE>

 This is document2.

 소스는 별로 어렵지 않으니 다큐먼트를 합치기가 귀찮다거나 아니면

 알고리즘을 수정하고 싶다면 간단히 수정해보아도 공부하는데 도움이

 될듯하다.

 기본적으로 소스에서는 IDF를 log2 ( N / DF )로 계산하고 있다.

#!/usr/bin/perl

use strict;

open(IN, "document.txt") or die;
my $nstory = -1;
my @words;
my %granddict;
my @weight;
my @unit;
my $i;
my $j;
my @cosine;
my $word;
my $sum;
my $df;
my @tf;
my $n;
my %df;
my $len2;
my $len;

#Step 1: Compute the term frequencies

while(<IN>){
    chomp;
    my $title;
    if ( /<TITLE>(.*)<\/TITLE>/ ){
        $title = $1;
        ++$nstory;
        print "Title of story $nstory = $title \n";
    } else {
        $_ = lc;
        s/--/ /g;
        s/ - / /g;
        s/[,.";!()?:_\[\]]//g;
        s/\s+/ /g;
        s/^\s+//g;
        @words = split(/ /);
        foreach $word (@words){
            if ($word =~ /^;?(.*?)'?$/){
                $word = $1;
            }
            ++$tf[$nstory]{$word};
            ++$granddict{$word};
        }
    }
}

foreach $word (sort keys %granddict ) {
    $sum = 0;
    for $i ( 0 .. $#tf ){
        if ($tf[$i]{$word} > 0){
            ++$sum;
        }
        $df{$word} = $sum;
    }
}

$n = $#tf + 1;
foreach $word (sort keys %granddict){
    for $i (0 .. $#tf){
        $weight[$i]{$word} = $tf[$i]{$word}*log($n/$df{$word})/log(2);
    }
}

for $i ( 0 .. $#tf ) {
    $len2 = 0;
    foreach $word ( sort keys %granddict){
        $len2 += $weight[$i]{$word}**2;
    }
    $len = sqrt($len2);
    foreach $word ( sort keys %granddict){
        $unit[$i]{$word} = $weight[$i]{$word}/$len;
    }
}

for $i ( 0 .. $#tf ) {
    for $j ( 0 .. $#tf ) {
        $sum = 0;
        foreach $word ( sort keys %granddict ) {
            $sum += $unit[$i]{$word} * $unit[$j]{$word};
        }
        $cosine[$i][$j] = $sum;
    }
}

print "\n";
for $i ( 0 .. $#tf) {
    for $j (0 .. $#tf) {
        printf "%.4f ", $cosine[$i][$j];
    }
    print "\n";
}

 참고로 소스의 출처는 Practical Text Mining With Perl 이란 책이다. 

 (저작권에 걸릴려나.. ) 

 책이 text mining에 관한 기초 실무로는 딱 좋으니 관심있는 분들은

 한번 보시라.