寫 ACM 的時候最好少用 C++ std

寫了一題用到 STL map 怎樣都過不了，拿掉 map 用其他方法後就過了，兩個用的是一樣的演算法，實在看不出來 map 版本哪邊有問題，也許 C++ 有太多隱藏地雷，不熟的人踩到都不知道怎麼死的

CreateToolhelp32Snapshot enumrate process 的順序

使用 CreateToolhelp32Snapshot 來枚舉 process 的順序是 pid 從小到大
並且循著 process tree 來枚舉

例如下面的 process tree



枚舉的 process pid 順序就會是
4, 580, 736, 4148, 832, 7212, 10444, 10452, 840,936

WCF Web service 傳輸資料量長度限制

之前使用到 WCF Web Serivce 時, 傳輸的參數大小如果超過某個數量就會發生 error.
web service 是以 HTTP protocol 傳輸資料, 印象中 HTTP POST method 沒有限制長度大小才是, 查了一下資料才發現其實是 IIS server 的限制.

Request Limits <requestLimits>

windows 8.3 filename

8.3 filename 是 DOS 時代的檔案命名規定  那時的 DOS FAT file system 只能支援最長 8 字元的檔名跟最長 3 字元的副檔名
不過到了 windows 時代的 FAT 跟 NTFS file system 就沒有這個限制了

但是為了相容的緣故 windows 還是支援 8.3 filename
例如創造一個長檔名的檔案 abcdefghi.xyz
windows 會幫忙建一個相對的 8.3 filename 存在 disk 上
像這樣 abcdef~1.xyz

所以有時會看到帶有 ~ 符號的檔名 而 ~ 後面的數字代表這個檔案有幾個
例如假設有兩個檔案
1. abcdefgh123.xyz
2. abcdefgh456.xyz

這兩個檔案相對的 8.3 filename 會是
1. abcdef~1.xyz
2. abcdef~2.xyz

不過這個功能是可以關掉的 所以不能認為每個系統上的 long filename file 都會有 8.3 filename
在 MSDN 上有詳細描述

java 的 volatile 和 synchronized

在 java 中有 volatile 和 synchronized 關鍵字
synchronized 應該蠻常使用到的 大家都知道是甚麼意思
但是 volatile 就可能比較少用 這個關鍵字是用來修飾 "基本型態" 的變數
保證這個變數在多執行緒時的同步

在這邊跟這邊有講到很有用的觀念
大意是在 java 中有主記憶體區域 而 thread 可以有自己私有的記憶體區域
某個 thread 中存取一個全域變數 可能會在存取完後將這個變數的值保存在自己私有的記憶體區域
這樣會造成多個 thread 存取全域變數時結果不同步
但是如果一個變數事前有用 volatile 修飾
則保證所有 thread 對這個變數做完存取時會將變數值寫回到主記憶體區域
這樣看似只要用 volatile 就可以完全保護好變數  其實不然
因為除非對這個變數的操作是 atomic operation
否則還是會出問題
像在第一個連結就有提到  java 中的 ++ 運算不是 atomic operation
所以如果多執行緒對某變數作 ++ 運算  就算用 volatile 還是不能保證變數的同步
因為 volatile 只能保證 thread 將值寫回主記憶體
並不能保證同一時間只有一個 thread 去存取這個變數
像是 ++ 不是 atomic operation 若是有個 thread 的 ++ 運算還沒做完 另一個 thread 是可以對這個變數作 ++ 的
只是他們都會把做完 ++ 的結果寫回主記憶體而已
這樣變數就未必會同步了

FindExecutable 對於尋找 file associated program 並不可靠

windows 系統會記住許多文件的預設處理程式 例如 txt 檔案預設就是用 notepad 開啟
如果要在程式中找出某個文件的預設處理程式 有一個很直觀的 API FindExecutable 可以用

但是這個 API 並不太可靠 一個 known issue 是在 XP 上對於附檔名 accdb 的文件就找不到處理程式
網路上的討論是這個 API 對於 3 個字元以上副檔名的檔案處理可能會發生問題

在我的 XP 系統上 不只 accdb 出問題 rmvb 檔案也出問題找不到預設處理程式
網路上有人用 procmon 監控發現這個 FindExecutable 在查詢 registry 時會把副檔名弄錯
我試了一下果然如此

當用 rmvb 為副檔名時 FindExecutable 用 rmv 去查 registry
當用 accdb 為副檔名時 FindExecutable 用 acc 去查 registry
不過為什麼會有這種 bug 就不知道了

一個替代方案是用 AssocQueryString API

TCHAR exe_path_buf[MAX_PATH] = {0};DWORD buf_size = MAX_PATH;AssocQueryString(0, ASSOCSTR_EXECUTABLE, ".accdb", "open", exe_path_buf, &buf_size);

經測試 rmvb 跟 accdb 都可以正常工作

GOT與PLT的運作

ELF(Executable and Linking)格式的執行檔 是利用PLT(Procedure Linkage Table)與 GOT(Global Offset Table)來處理函式庫中的函式呼叫
(呼叫使用者自定義函式則不會使用到PLT及GOT)
例如 若是一個執行檔中有呼叫到printf函式 程式在第一次呼叫到此函式時 會跳到PLT中的printf函式entry
組合語言長的像這樣:

080482c8 < printf@plt >: 80482c8:       ff 25 d4 95 04 08       jmp    *0x80495d4 80482ce:       68 18 00 00 00          push   $0x18 80482d3:       e9 b0 ff ff ff          jmp    8048288 <_init+0x18>

第一個jump指令 跳到GOT中與printf相關的entry(0x80495d4)所包含的記憶體位址 這個位址在ELF執行檔load time的時候會被dynamic linker填入第二個push指令的位址
這個push指令將某個資料push入stack(這個資料之後dynamic linker會用到) 然後第三個jump指令跳到PLT0的位址(代表PLT第一個entry)
所以 任何函式 在"第一次"執行時 都會直接跳到第二個push指令 然後跳到PLT0去執行 PLT0長的像這樣

08048288 <__gmon_start__@plt-0x10>: 8048288:       ff 35 c0 95 04 08       pushl  0x80495c0 804828e:       ff 25 c4 95 04 08       jmp    *0x80495c4 8048294:       00 00                   add    %al,(%eax)

PLT0所做的事情 第一個push也是將某個資料push入stack(之後dynamic linker會用到)然後跳到dynamic linker去解析出printf函式的位址
作解析的動作需要額外資訊 也就是先前那兩個push指令push到stack的資料 等解析出printf函式的位址後 將位址存放到GOT中的printf相關entry 也就是0x80495d4中
之後再呼叫到printf時 一樣跳到0x80495d4中存放的位址 此時這個位址已經是printf函式的位址 也就不會跳到PLT0 一切正常運作

而為什麼要這樣作 根據linker and loader中所說 因為一個program可能會包含很多他有可能不會呼叫到的函式
所以 為了加速程式的起始速度 在load time不會解析出所有函式的位址
改而在run time第一次執行到該函式時 才解析出函式位址來用 而這稱為lazy evaluation

printf, wprintf output unicode to console

連結
一篇說明 printf 跟 wprintf 輸出 unicode 到 console 的一篇文章
解釋的非常詳細

windows API StringCchCopy

HRESULT StringCchCopy( _Out_ LPTSTR pszDest, _In_ size_t cchDest, _In_ LPCTSTR pszSrc);

這個 API 有一個回傳值是
STRSAFE_E_INSUFFICIENT_BUFFER

這個值代表的意思是 dest buffer 太小了不足以放入 source buffer 裡面的字串
但是這個API還是會幫你把 source 裡的字串截斷後放入 dest buffer 裡面

我有點好奇
StringCchCopy 知道 dest buffer 大小就算了 它怎麼會知道 source buffer裡面的字串大小?

後來經過實驗 它會去偵測 source buffer 裡面的內容直到找到 '\0' 結尾 以此判斷來源字串大小
以下的 code 得以證實
第二次的結果就不會是 STRSAFE_E_INSUFFICIENT_BUFFER

#include <cstdio>#include <tchar.h>#include <StrSafe.h>int main(){  TCHAR buf[5] = {'a', 'b', 'c', 'd', 'e'};  TCHAR src[6] = {'1', '2', '3', '4', '5', '\0'};    HRESULT result = StringCchCopy(buf, 5, src);  if (STRSAFE_E_INSUFFICIENT_BUFFER == result)    puts("STRSAFE_E_INSUFFICIENT_BUFFER");  else    printf("%s\n", buf);  TCHAR src2[6] = {'1', '2', '3', '4', '\0', '5'};  result = StringCchCopy(buf, 5, src2);  if (STRSAFE_E_INSUFFICIENT_BUFFER == result)    puts("STRSAFE_E_INSUFFICIENT_BUFFER");  else    printf("%s\n", buf);  return 0;}

atomic operation

所謂的atomic operation在這邊有說明
簡單來說一個 atomic operation 就是不會被打斷的操作
一般來說可以看成是組語的一道CPU指令
一個指令不是做完就是沒做 不會有做到一半的情形

而有時候看到 atomic 用來形容一個 function
就表示該 function 同一時間內只有一個 thread 可以進入
例如 linux 的 open system call

android boot process

1.power on and boot ROM code execution
    一開始可用的 ram 只有 internal ram
    電源 ok 時會從 boot ROM code 開始執行 這是在 CPU 硬體內建的 code
    boot ROM code 會偵測 boot media 中的 boot loader 並把它 load 到 internal ram 中
    跳到 boot loader 執行

2.boot loader
    boot loader 是用來設定及初始化 memory 並且 load kernel 到 memory 中
    boot loader first stage 一開始偵測並設定 external ram (boot loader 太大時就會分為兩份 1st stage boot loader 會塞到 MBR 中的前 446 bytes)
    設定完成便 load main boot loader(second stage boot loader) 到 external ram
    second stage boot loader 會設定 file system, memory, network support, 還有可能設定 low level memory protections and security options
    接著就從 boot media 中把 kernel load 到 ram 中
    load kernel 完成便跳到 kernel 執行

3.linux kernel
    kernel 設定系統要 run 起來一切所需的事情, interrupt controllers, memory protections, cache and scheduling
    等到 MMU and cache 初始化之後系統可以用 virtual memory 和 啟動 user space process
    kernel 去 system/core/init 下找 init process 並且啟動它成為第一個 user space process

4.init process
    init process 是系統裡所有 process 的祖先
    init process 會去找 init.rc 檔 這是一個 描述一些system service, file system, 或是參數的 script
    init process 去 parse init.rc 並且啟動 system service processes

5.Zygote and Dalvik
    Zygote 被 init process 啟動並且初始化 Dalvik VM

6.the system server
    system server 是系統中第一個跑起來的 java 元件
    他會啟動一些 android service 像是 telephony service 和 bluetooth
    啟動的 service 都寫在 system server 的 run method 裡面 system server 的 source code 就在 frameworks/base/service/java/com/android/server/SystemServer.java

7.boot complete
    一但 system server 跑起來而且系統 boot 完成就會有一個 broadcast action 叫做 ACTION_BOOT_COMPLETE
    在你的 application 中 register 要接收這個 broadcast 就可以在系統 boot 完成後啟動你自己的 service

資料來源:
http://www.androidenea.com/2009/06/android-boot-process-from-power-on.html

android 的 service

android 的 service 有分為兩類(這裡討論的不是在寫 android 應用程式時用的 service)
1. android service
2. native service
在 jollen 的 blog 還有 android1.net 都有說明

此外 android 在 booting 時會啟動一些 service
android 的啟動流程在這裡也講得很清楚
依照 init.rc 所寫 init process 啟動 service manager 和 zygote 之後
似乎還會啟動很多 native service (eq: dbus)
只是這些 service 應該 application 的開發者是完全不需要關心的

zygote 會啟動 system server
在這裡可以看到 system server 是用 java 實做 run 在一個叫 system_process 的 process 裡
system server 首先載入 android_servers 這個 library (c++實做 code 在 frameworks/base/cmds/system_server/library/system_init.cpp)
然後用 init1() 這個 jni method 去呼叫 system_init() 函式
system_init() 函式會啟動一些 native service 然後呼叫 system server 的 init2() 函式
init2() 函式接著啟動 android service 例如 power manager  window manager
從這張圖可以看到 被 init2() 函式啟動的 android service 都是 run 在 system_process 中的一條 thread 裡

android 的 user space HAL

網路上一個有關user space HAL的問題
Q:
Hi All,

  I would like to know if there is any documents or related web links
for device driver development on "User Space Abstraction Layer ".
  I would appreciate if anyone can give me how this really works in
real world scenario.

 Thanks...

A:
I would suggest you to have a look of the overlay code in
hardware/libhardware/moudule/overlay.
In the new HAL architecutre, it introduced a "stub" concept which replaced
the legacy architecture which load the c/c++ library from java
application/service directly. In "stub", you need to implement some
interfaces and provide them to hardware service. For example if you wanna
implement a LED, the architecture will be:
Kernel Driver (driver to control the LED hardware) <-> syscall (open, close,
ioctl for LED, etc.) <-> hardware/libhardware/module/led (the led HAL
interfaces or "stub" ) <-> framework/base/services/jni/
com_android_server_LedService.cpp (the java native interface for LED )<->
framework/base/service/java/com/android/server/LedService.java (the java
interface of LED service <-> framwork/base/core/java
/android/hardware/LedManager (the java code of LED manager) and
ILedService.aidl (the android interface description language file for LED)
<-> LED application

這裡有一個文章連結

jollen的blog也有相關介紹文章

android 的 local service 與 thread 的差別

android 官網中提到要執行 background 的 long running 動作時 最好要用 service
但是 service 既然也是在同一個 process 中 create 一個 thread 來做這些 long running 的動作
為什麼不直接在 activity 裡直接 create thread 來做就好了

在官網最下面有解答
1.
    一個有 service 在跑的 process 權限會比只有 background activity 在跑的 process高
    也就是當系統要砍 process 的時候比較不容易砍到你

2.
    用 service 的話 不管 activity 發生什麼事 都不會影響到 service, process 最少可以是 "service process" priority

android的application component是run在哪個thread

依照 android 官網所說 android 的 application component 包括 activity service broadcast receiver 等等
都是 run 在同一個 linux process 之中(除非這些 component 有特別指名要 run 在其他 process, 可以在 androidmanifest.xml 中指定)

官網又有說到 所有這些 component object 的實例化都發生在 process 的 main thread 中
而且有關 life cycle 的 method (例如 onCreate) 也都是在 main thread 中執行
所以在這些 method 中不能執行太花費時間的動作 免得阻擋到其他 component 的執行
如果需要作這些動作 應該 create 其他 thread 來做

vim 的自動完成

vim 也可以有自動完成的功能
在ubuntu 10.04下面裝的 vim 7 有預設支援自動完成的語言的資訊在 /usr/share/vim/vim72/autoload/ 下面

以php 為例 要開啟 php 自動完成功能 只要在 .vimrc 裡加上一行
    autocmd FileType php set omnifunc=phpcomplete#CompletePHP
就可以了

接下來在編輯 php 檔案時 只要用 ctrl+x ctrl+o 就可以使用自動完成

但是我最需要的 C/C++ 語言似乎需要額外的套件支援才能使用自動完成

C 的話有關鍵字自動完成可以用 不用在 .vimrc 中設定任何選項
只要在編輯 c 檔案時有 include 任何標頭檔 例如 stdio.h
在打入 print 時按下 ctrl+p 就會從 stdio.h 中找出符合的函式供你挑選

C++的話就沒有了 完全需要額外套件的支援
不知道為什麼 vim 不預設支援標準函式庫的自動完成 明明這是最需要的
關於 C/C++ 的自動完成之後再研究

vbscript 物件的解構函式不會在頁面關閉時呼叫

在VBScript裡面 可以寫下你自己物件的建構函式與解構函式
但是必須了解的一件事是 如果VBScript是跑在一個網頁上 網頁關閉時不會呼叫VBScript的解構函式
我本來以為 頁面關閉 物件銷毀 解構函式應該會執行 但是事實並不是如此
不過還好 還有 window.onbeforeunload 事件可以用
還是有機會在頁面結束前 作一些你想要執行的動作的

css 的 width 和 height 用百分比表示

在 css 裡面 元素的 width 和 height 可以用百分比表示
代表這個元素的寬和高為父元素的百分比
但是因為是使用父元素的寬和高來當基準 一定要確定父元素的寬和高也正確的設定了
否則可能會出現排版亂掉的情況

VBScript 和 JavaScript 的 string 是 pass by reference

在寫 scripting language 時 都知道變數通常可分為 primitive type 跟 reference type
primitive type 是 pass by value 而 reference type 是 pass by reference
可能語言會宣稱自己只有 pass by value (例如 java, 雖然他不是 scripting 語言)
但是保持一個觀念就是 reference type 的變數被傳進一個函式後
函式對這個變數做的改變在函式退出後還可以看的到

不過對 javascript 和 vbscript 來說 string 是特別的 string 不是物件 所以他是 primitive type
但是 string 又可以是任意長度的 所以如果 string 如果是 pass by value 將會很沒有效率
所以在實作上通常把他作為 pass by reference

如果只用 primitive type 和 reference type 來 分別 pass by value 和 pass by reference
可能會對 string 的 pass rule 搞錯了

vbscript default method 和 default property

在VBScript裡面的class可以有所謂 default method 和 default property 他的作用是可以讓人不需要用 method name 或 property name 就可以呼叫
此外一個class 只能有一個 default method 和 default property 否則會造成錯誤

如以下例子為 default method

class FOO
    public default function no_name
        msgbox "default function called"
        no_name = "i am FOO"
    end function
end class

dim o : set o = new FOO
msgbox o()
  
以上的程式會跳出兩個msgbox 可以得知 no_name 在執行到 o() 時被呼叫

在VBScript 裡面的 dictionary 還有 collection 物件都有 default property
collection 和 dictionary 的 default property 就是 Item property
可以讓人在 coding 時方便許多
例如 要在 dictionary 取一個 key 是 "kerker" 的 value
嚴謹的寫法是 dict.Item("kerker")
但是因為 default property 的關係 用 dict("kerker") 也可以 這樣用起來就方便多了

不過網路上關於 VBScript 的 default method, default property資料好像蠻少的 而且有人說最好不要用這個特性
因為這樣會讓寫出來的code 難以閱讀