커널버젼2.4대에서 __free_pages_ok() 함수에 질문이 있습니다.(

ktshipme의 이미지

커널 프로그래밍 폴더가 없어져버렸네요.. 흠..

리눅스 커널 2.4.20에서
__free_pages_ok()함수를 보면 mask를 사용하여서 2의 order승을 계산하는 방법을 쓰잖습니까?
음...

82 static void __free_pages_ok (struct page *page, unsigned int order)

........

115         zone = page_zone(page);
116 
117         mask = (~0UL) << order;
118         base = zone->zone_mem_map;
119         page_idx = page - base;
120         if (page_idx & ~mask)
121                 BUG();
122         index = page_idx >> (1 + order);
123 
124         area = zone->free_area + order;
125 
126         spin_lock_irqsave(&zone->lock, flags);
127 
128         zone->free_pages -= mask;
129 
130         while (mask + (1 << (MAX_ORDER-1))) {
131                 struct page *buddy1, *buddy2;
132 
133                 if (area >= zone->free_area + MAX_ORDER)
134                         BUG();
135                 if (!__test_and_change_bit(index, area->map))
136                         /*
137                          * the buddy page is still allocated.
138                          */
139                         break;

................................

128번째 줄에 보시면
128 zone->free_pages -= mask;
여기서 -mask는 2의 order승이 되므로 free_pages에 2의order승을 더하는 것이다.. 라고 이해도 되고, 어떤 매뉴얼을 찾아봐도 그런식으로 얘기해주고 넘어가는데..

order가 0이면 1이, 1이면 2, 2이면 4가.. .. 더해지게 되겠죠?(mask = (~0UL) << order;) 이니깐요..

하지만 이건 2의보수 시스템에서만 해당되는게 아닌가요? 1의보수이면 order가 2이면 -mask는 4가 아니라 3이 될테니.... 각각 더해지는 page수가 1이 부족해질거 같은데... /mm/page_alloc.c 의 소스니깐 분명 시스템 독립적이라고 생각되어지는데요...
1의 보수 시스템에서는 이것이 어떻게 실행이 가능해지는지 궁금합니다.

혼자 해결해볼려고 용을 써봤는데.. 모르겠군요... 2.6커널에서 이 함수 소스를 찾아보니.. 좀 간단히 생각해도 1의 보수 시스템에서 돌아갈 수 있겠구나... 하고 생각될만하게 바뀌었네요.. 이게 어떻게 돌아가는 겁니까? 에휴.... 주름살이 느는거 같군요..

hwandori의 이미지

먼저 거기까지 생각하시고 공부하시는 모습에 고개 숙여집니다..

저도 그코드를 분석한적 있지만 1의 보수를 쓰는 머신까지 생각하지

못했는데... 검색중 이런걸 발견했는데..

http://seclists.org/lists/linux-kernel/2000/Mar/1777.html

전혀 관계없는 얘긴지 모르겠지만 저도 궁금해지네요...^^

pastime의 이미지

저도 모든 시스템을 다 알지 못하니 확실히 말씀드릴 순 없지만
2.4.20 에서 지원하는 머신들이 모두 2의 보수 형식을 사용하는게 아닐까요..?

doldori의 이미지

zone->free_pages와 mask는 무부호형입니다. 무부호형의 경우 연산 결과는
정수형의 내부 표현 방법과는 무관하게 2^n의 modulo로 정의되기 때문에
1의 보수냐 2의 보수냐로 결과가 달라지지는 않습니다. (유부호형이면 그런 보장은
못합니다만.) 즉 위의 코드에서 order가 2이면 항상 4를 더하는 것과 같습니다.

hwandori의 이미지

^^ 자료형을 유심히 못봤었네요.... 덕분에 잘 알았습니다..

익명 사용자의 이미지

며칠째 KLDP가 안되서... 못들어오고 있었는데..
음...

Quote:
무부호형의 경우 연산 결과는 정수형의 내부 표현 방법과는 무관하게 2^n의 modulo로 정의되어있다...
흠..
무보호형의 연산결과는 2^n의 modulo 가 된다...

즉 free_page - mask = 2^n의 modulo 이다.

이해가.....안되네요.. 하하하 민망하군요. :oops:

보충 자료라도...부탁드립니다.

doldori wrote:
zone->free_pages와 mask는 무부호형입니다. 무부호형의 경우 연산 결과는
정수형의 내부 표현 방법과는 무관하게 2^n의 modulo로 정의되기 때문에
1의 보수냐 2의 보수냐로 결과가 달라지지는 않습니다. (유부호형이면 그런 보장은
못합니다만.) 즉 위의 코드에서 order가 2이면 항상 4를 더하는 것과 같습니다.
ktshipme의 이미지

위의 손님은 접니다..하하 로긴을 안했군요~
2^n 의 modulo라는 식은 어떤 값이 나올거라고 치고( 배웠던거 같긴한데.. 대학때 열심히좀할껄..) 무보호형끼리의 연산은 그렇게 정의 되어있다... 라는 것은 C의 표준인가요? 아님 컴구조상 그런것인가요? 어째서 그렇게 되어있는지 궁금하네요.

doldori의 이미지

Anonymous wrote:
흠.. 무보호형의 연산결과는 2^n의 modulo 가 된다...

즉 free_page - mask = 2^n의 modulo 이다.

이해가.....안되네요.. 하하하 민망하군요. :oops:

보충 자료라도...부탁드립니다.


modulo는 나머지를 뜻합니다. 이들 변수의 형은 unsigned long입니다.
이들이 표현할 수 있는 값은 0 ~ ULONG_MAX인데 이것은 (ULONG_MAX + 1)로
나누었을 때 나머지의 범위도 되지요. 이런 특성 때문에 무부호형의 연산 결과는
wrap-around 되고 따라서 overflow가 일어나지 않습니다. (0으로 나누는 것은 제외)

ktshipme wrote:
무보호형끼리의 연산은 그렇게 정의 되어있다... 라는 것은 C의 표준인가요? 아님 컴구조상 그런것인가요? 어째서 그렇게 되어있는지 궁금하네요.

표준에서 정해진 것입니다. 그 이유는 다음을 참고하십시오.

http://www.woong.org/board/?doc=bbs/gnuboard.php&bo_table=qna&sselect=wr_subject%7Cwr_content&stext=modulo&soperator=0&page=1&wr_id=151

ktshipme의 이미지

감사합니다.
대단한 실력을 지니신 분이군요. 고개가 절로 숙여집니다.

죄송합니다. 이해는 되었는데.. 적용이 잘 안되네요..

Quote:
연산 결과는 wrap-around 되고 따라서 overflow가 일어나지 않습니다.

정반대로 말하는 것이지만 결국은 무부호형 정수는 overflow예외가 발생할 경우 스스로 로테이션(wrap-around)된다.... 라고 이해가 됩니다. 즉 overflow가 일어나지 않으면 별반 다를것이 없다는 거겠지요?

그럼 아래 부분에서 어느부분에서 overflow가 일어난 것이죠?

117         mask = (~0UL) << order; 

128         zone->free_pages -= mask; 

이므로 예를 들어 두 변수 다 8비트 unsigned char 라 하고 zone->free_pages가 현재 8이고 order는 2라고 했을때,
120 에서 mask = 1111 1100 이고
128 에서 0000 1000 -= 1111 1100 이면...

zone->free_pages = 0000 1000 - 1111 1100 이므로 결국,
-> zone->free_pages = 0000 1000 + 0000 0011 (1의보수 시스템이므로)
이 되서 0000 1011 이 되버리네요.. ㅠ.ㅠ 11.. 흠..

제가 어느부분에서 착각을 하고 있는 거죠? 오버플로우가 일어나는게 안보이는데... ( - 1111 1100.. 이것을 내부적으로 변환할때 이미 일어나는 것인가.... 추측은 금물!! )

doldori의 이미지

ktshipme wrote:
zone->free_pages = 0000 1000 - 1111 1100 이므로 결국,
-> zone->free_pages = 0000 1000 + 0000 0011 (1의보수 시스템이므로)
이 되서 0000 1011 이 되버리네요.. ㅠ.ㅠ 11.. 흠..

이 부분이 잘못 되었습니다. - 연산은 산술 연산이므로 비트 연산으로 바꿔서
생각하면 안됩니다. 모두 unsigned char형이고 UCHAR_MAX == 255라고
가정할 때, zone->free_pages가 8이고 order가 2라면 117 라인의 결과로
mask의 값은 0xfc, 즉 252가 됩니다. 그리고 128 라인에서 8 - 252, 즉 -244가
되지요. 그런데 무부호형은 wrap-around 되므로 여기에 256을 더하여 최종 결과는
12가 되는 것입니다. 다시 말씀드리지만 산술 연산을 할 때는 내부적인 비트 표현은 잊으세요.
ssehoony의 이미지

doldori wrote:
ktshipme wrote:
zone->free_pages = 0000 1000 - 1111 1100 이므로 결국,
-> zone->free_pages = 0000 1000 + 0000 0011 (1의보수 시스템이므로)
이 되서 0000 1011 이 되버리네요.. ㅠ.ㅠ 11.. 흠..

이 부분이 잘못 되었습니다. - 연산은 산술 연산이므로 비트 연산으로 바꿔서
생각하면 안됩니다. 모두 unsigned char형이고 UCHAR_MAX == 256이라고
가정할 때, zone->free_pages가 8이고 order가 2라면 117 라인의 결과로
mask의 값은 0xfc, 즉 252가 됩니다. 그리고 128 라인에서 8 - 252, 즉 -244가
되지요. 그런데 무부호형은 wrap-around 되므로 여기에 256을 더하여 최종 결과는
12가 되는 것입니다. 다시 말씀드리지만 산술 연산을 할 때는 내부적인 비트 표현은 잊으세요.

wrap-around 라... 처음 들어보는 용어군요. 좋은거 배웠습니다. ^^
근데 -244 에 256 을 더해서 12 가 되는게 맞는건가요?
-244에 255를 더해서 11이 되는건 아닌가요?

doldori의 이미지

ssehoony wrote:
근데 -244 에 256 을 더해서 12 가 되는게 맞는건가요?
-244에 255를 더해서 11이 되는건 아닌가요?

256을 더하는 것이 맞습니다. modulo 256이기 때문입니다.
간단히 생각해서 modulo 10인 경우 2, 12, 22, -8, -18 등은 모두 같은 집합에 속합니다.
ktshipme의 이미지

감사합니다. :D

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.