从5900到65535之间随机分配一个数字——erlang实现

vnc是一款开源的远程控制软件，它能完整的将窗口界面，通过网络传输到另外一台计算机的屏幕上。在linux下，vnc包括四个命令：vncserver,vncviewer,vncpasswd,vncconnect。在连接一台计算机的时候，需要知道对方计算机的IP和端口号，在我们的项目中，虚拟机的端口号是由master分配的，因此，master就要实现vncport的分配了，vncport的分配范围一般在5900到65535之间。

之前写的vncport的分配是用mnesia数据库来进行的，分配一个port之后在数据库中进行标记，也没有涉及比较复杂的算法，这种方法可以实现所要求的功能，但是在这将近65536个数据当中，每次要找一个没有使用的数据，这个时间也是比较长的。

后来，在学习进程的pid号分配的时候，也涉及到了这个问题，不过进程的pid分配范围是在0到32767之间，上面的数目是这个数目的２倍。因此，想借用内核中的pid分配算法（pid位图）来实现这里的vncport分配问题。

先来看一下pid位图算法：

为了表示32768个进程号是不是分配出去没有，我们要占用32768/8=4096个字节来标识，用每一位来标记一个pid号是不是分配出去。为此，我们可以定义一个这样的结构体：

typedef struct pidmap 

{

    unsigned int nr_free;

    char page[4096];

} pidmap_t;

用nr_free表示未分配出去的pid号的数目。

如果要根据一个给定pid号，要找它在这个结构体当中所对应的位的时候，可能我们首先想到的是下面的这个算法：

我们把上面的存放位图的变量想像成一个4096行，８列的表。首先给pid除以8，然后取整，即int a=(pid/8)，将得到的a的值作为pidmap.page的下标，也就是pidmap.page[a]，然后用int b=(pid%8)得到对应位的0—7之间的编号，这样的话，就唯一确定了一个pid编号在pidmap.page中的具体位置。

这个方法也是可以实现的，但是内核当中是通过移位操作来实现的。我们可以抽象出一张表，这个表有32列，1024行，这个刚好是一个页的大小。这个时候，我们可以通过pid的后5位值（变化范围在0—31之间）来确定在某一行的具体的列。通过pid的高27位（pid本身是32位的）来表示在具体的某一行。所以我们可以通过移位操作来实现。

具体的移位操作主要有两句：

unsigned long mask = 1UL << (offset & 31);

unsigned long *p = ((unsigned long*)addr) + (offset >> 5);

其中的offset表示的是一个要处理的pid号。

这样就可以实现了。

有关的详细的解释以及应用可以看我的博客：

http://blog.chinaunix.net/space.php?uid=22566367&do=blog&id=2845765

下面开始erlang中的vncport的分配。

Erlang 是面向函数式编程的，进程本身没有全局变量，在函数上下文中，可有局部变量，所有的局部变量都是readonly，并只能被赋值一次。因此，为了保存这个位图，可以借助数据库进行保存。

-record(vncport, {vnc_id, vnc_value}).

数据库弄两列，一列是vnc_id，一列是vnc_value。在这个数据库的每一项中，vnc_id表示的是vncport的一个地址，具体对应的是某一个vncport的高11位（65535是16位）；而vnc_value是一个32位的数据，用来表示32个vncport。

具体程序代码是：

%% File: vncport.erl
%% Created: 2011-10-18
%% Description:
-module(vncport).
-date("2011.10.18").

%%
%% Include files
%%
-include_lib("stdlib/include/qlc.hrl").

%%
%% Export functions
%%
-export([start/0, stop/0, set_bit/1, get_next_vncport/0, free_vncport/1]).

-record(vncport, {vnc_id, vnc_value}).

%%
%% API functions
%%
start() ->
    mnesia:stop(),
    mnesia:delete_schema([node()]),
    mnesia:create_schema([node()]),
    mnesia:start(),
    mnesia:create_table(vncport, [{attributes, record_info(fields, vncport)}]),
    vncport_init(),
%    mnesia:dirty_update_counter(vncport, last_used, -1),
    F = fun() ->
            Row = #vncport{vnc_id=last_used, vnc_value=-1},
            mnesia:write(Row)
        end,
    mnesia:transaction(F),
    io:format("mnesia start~n"),

    alloc_vnc(0, 5900).

stop() ->
    mnesia:stop().

get_next_vncport() ->
    %%  find last used vncport
    F = fun() ->
            Query = qlc:q([X#vncport.vnc_value || X <- mnesia:table(vncport), X#vncport.vnc_id =:= last_used]),
            [E] = qlc:e(Query),
            io:format("Last used vncport is:~p~n", [E]),
            E
        end,
    {atomic, R} = mnesia:transaction(F),
    Result = R+1,
    io:format("init vncport value is ~p~n", [Result]),  %% debug info
    search(search, Result).

free_vncport(N) ->
    Mask = 1 bsl (N band 31),
    Address = N bsr 5,
    io:format("Mask:~p, Address:~p~n", [Mask, Address]),  %% debuf info
    F = fun() ->
            Query = qlc:q([X#vncport.vnc_value || X <- mnesia:table(vncport), X#vncport.vnc_id =:= Address]),
            [E] = qlc:e(Query),
            Value = E band (bnot Mask),
            New = #vncport{vnc_id=Address, vnc_value=Value},
            mnesia:write(New)
        end,
    mnesia:transaction(F).

set_bit(N) ->
    Mask = 1 bsl (N band 31),
    Address = N bsr 5,
    io:format("set number:~p~n", [N]),  %% debuf info
%    io:format("Mask:~p, Address:~p~n", [Mask, Address]),  %% debuf info
    F = fun() ->
            Query = qlc:q([X#vncport.vnc_value || X <- mnesia:table(vncport), X#vncport.vnc_id =:= Address]),
            [E] = qlc:e(Query),
            Value = E bor Mask,
            New = #vncport{vnc_id=Address, vnc_value=Value},
            mnesia:write(New),
            io:format("update over :~p  ~p~n~n", [Value, New])  %% debug info
        end,
    mnesia:transaction(F).

%%
%% Local Functions
%%
vncport_init() ->
    F = fun(N) ->
            init_one_vncport(N)
        end,
    for(0, 2047, F).

init_one_vncport(N) ->
    Row = #vncport{vnc_id=N, vnc_value=0},
    F = fun() ->
            mnesia:write(Row)
        end,
    mnesia:transaction(F).

search(over, N) ->
    io:format("vncport ~p can use~n", [N]),
    ok;
search(search, 65536) ->
    io:format("search ~n"),
    search(search, 0);
search(search, Vncport) ->
    io:format("search ~p~n", [Vncport]),
    case is_empty(Vncport) of
        true ->
            set_bit(Vncport),
            update_dirty(Vncport),
            search(over, Vncport);
        false ->
            Next = Vncport+1,
            search(search, Next)
    end.

is_empty(Vncport) ->
    io:format("begin check~n"),
    Mask = 1 bsl (Vncport band 31),
    Address = Vncport bsr 5,
    F = fun() ->
            Query = qlc:q([X#vncport.vnc_value || X <- mnesia:table(vncport), X#vncport.vnc_id =:= Address]),
            [E] = qlc:e(Query),
            Result = E band Mask,
            if
                Result =:= 0 ->
                    true;
                true ->
                    false
            end
        end,
    {atomic, R} = mnesia:transaction(F),
    io:format("over check, result is ~p~n", [R]),
    R.

update_dirty(Vncport) ->
    Row = #vncport{vnc_id=last_used, vnc_value=Vncport},
    F = fun() ->
            mnesia:write(Row)
        end,
    mnesia:transaction(F).

for(Max, Max, F) ->
    [F(Max)];
for(Min, Max, F) ->
    [F(Min)|for(Min+1, Max, F)].

alloc_vnc(Min, Min) ->
    io:format("alloc last vnc:~p~n", [Min]),
    set_bit(Min);
alloc_vnc(Min, Max) ->
    io:format("alloc vnc:~p~n", [Min]),
    set_bit(Min),
    alloc_vnc(Min+1, Max).

API接口说明：

start()：初始化数据库。

stop()：关闭数据库。

set_bit(N)：将Ｎ这个vncport端口号置为不可用。

get_next_vncport()：得到一个可以分配的vncport端口号。

free_vncport(N)：释放vncport为Ｎ的这个端口号。