ポリゴン処理

著者: momokuri Eメール

分散タイルサーバを実現するTileManプロジェクトで、つかうため lua-nginx-osm ライブラリというのを、コアライブラリとして開発しています。

この中で、次のような機能を実現しています。

  1.  ポリゴン指定した地域をデータとして持っている。
  2. タイルサーバで、タイル要求されたX/Y/Zoomについて、 そのタイルが、(1)の地域に含まれているかどうかを判定する。
  3. 含まれている場合、タイルを生成する。

地域データは、geofabrikのデータを意識しています。

DBとして、特定の地域のデータだけPostGISに持っておいて、タイル要求がきたときに、それがDBに入っていればレンダリング実施、そうでなければ、アップストリームのtile.openstreetmap.orgへ要求、みたいな処理を実現しています。

typical configuration of tileman

これは、他の製品でもありそうな機能ですよね。

さて、上記の処理を行うために、is_inside_regionという関数を定義しました。計算速度を上げるために、
簡易なアルゴリズムを採用しました。ポイントは以下です

res = (y1 - y2) * nx + (x2 - x1) * ny + x1 * y2 - x2 * y1

(x1, y1) (x2, y2) は、地域を指定するポリゴンの一辺のベクトル
(nx, ny)は、判定するタイル要求の位置

上記は外積をとっており、全ての辺について判定して、すべて負でなければ、
すべての辺の内側に、判定するタイル要求の位置があることが分かります。

しかし、この判定ロジックには、弱点があり、比較するポリゴンは、かならず
convex polygon (凸多角形)である必要があるのです。

そこで、たとえば japan.kmlのような凹凸多角形(concave polygon)を凸多面体に分割することにしました。
単純なケースでは、手作業でも可能ですが、複雑になると、手作業では不可能になります。

このような問題は、計算幾何学で研究されていて、素晴らしいライブラリがすでに提供されています。
例えば、アルゴリズム設計マニュアルの下巻には、第17章計算幾何学の中に、17.11多角形分割 として解説されており、CGALというライブラリがつかえることが記されている。また、上記の判定についても、17.7 点位置決定で詳細に書かれている。

そこで、CGALを用いて、ポリゴンを複数の多角形に変換し、LUAのプログラムを生成するようなユーティリティプログラムを書くことにしました。

$ git clone https://github.com/miurahr/lua-nginx-osm.git
$ cd lua-nginx-osm
$ apt-get install libcgal-dev cmake make
$ make

これでプログラムが生成されるはずです。実行は、

$ utils/poly2lua/poly2lua -t

ここで(-t)をつけると、テストモードで、内蔵の日本の定義データを元に、複数の多角形(緯度経度)を示すデータを生成します。
また、osm/data/*.kml が元データで、 osm/data/*.luaが生成された複数の凸多角形のデータです。

貧乏になるということ。

著者: momokuri Eメール

リンク: http://d.hatena.ne.jp/monyakata/20130105/1357342795

会社やめていないけど、しまむらとユニクロを来て、忘年会と新年会の出費と投資対効果を考えている自分は、貧乏根性が板についてきたかしら...

時間コストと、移動コストと、市場価格を計算しながら買い物するのは貧乏だからかというと、仕事での購買でも同じようなことをやっていることに気づいたり。購買の見積もりと市場価格を睨みながら、人件費(時間コスト)と効果を比較して決定していく。

世の中の企業で、利益を上げているところは、結構シビアにやっていると思うのだが、家計でもやったらいいんだろうと思う。安ければいいではなくて、時間との見合いではあるけどね。

あ、そうそう。自由であることは、コストのかかることだよね。 会社やめて900万円減で、"自由"になったという事は、平日平均10時間を年間200日自由にしたとして、一時間あたり4500円で(みなし)買ったという事だ。 つぎに自分の時間を、会社か顧客に売るまでは。:)

もしかしたら大変な贅沢かもしれない。

Linux kernel Hyper-V and Virtual-PC detection

著者: momokuri Eメール

Recent kernel detect MS Hyper-V and use VMBUS technology for disk access. It works fine on Hyper-V VMM but kernel mis-detect Virtual-PC on Windows 7. Because there is not VMBUS technology in Virtual-PC, so kernel cannot find root disk and fails to boot. Kernel should detect Virtual-PC than Hyper-V. It is known that Hyper-V has a bios vendor name 'VRTUAL' now but it is easily changable. Patch is as follows: /drivers/ata/ata_piix.c
static int prefer_ms_hyperv = 1;
 module_param(prefer_ms_hyperv, int, 0);
 
 static void piix_ignore_devices_quirk(struct ata_host *host)
 {
 #if IS_ENABLED(CONFIG_HYPERV_STORAGE)
 	static const struct dmi_system_id ignore_hyperv[] = {
 		{
 			/* On Hyper-V hypervisors the disks are exposed on
 			 * both the emulated SATA controller and on the
 			 * paravirtualised drivers.  The CD/DVD devices
 			 * are only exposed on the emulated controller.
 			 * Request we ignore ATA devices on this host.
 			 */
 			.ident = "Hyper-V Virtual Machine",
 			.matches = {
 				DMI_MATCH(DMI_SYS_VENDOR,
 						"Microsoft Corporation"),
 				DMI_MATCH(DMI_PRODUCT_NAME, "Virtual Machine"),
+				/* DMI_MATCH(DMI_BIOS_VENDOR, "VRTUAL"), */
 			},
 		},
 		{ }	/* terminate list */
 	};
+	static const struct dmi_system_id find_virtual_pc[] = {
+		{
+			.ident = "Microsoft Virtual-PC",
+			.matches = {
+				DMI_MATCH(DMI_SYS_VENDOR,
+						"Microsoft Corporation"),
+				DMI_MATCH(DMI_PRODUCT_NAME, "Virtual Machine"),
+				DMI_MATCH(DMI_BIOS_VENDOR, "American Megatrends Inc."),
+			},
+		},
+		{ }	/* terminate list */
+	};
 	const struct dmi_system_id *dmi = dmi_first_match(ignore_hyperv);
 
 	if (dmi && prefer_ms_hyperv) {
-		host->flags |= ATA_HOST_IGNORE_ATA;
-		dev_info(host->dev, "%s detected, ATA device ignore set\n",
-			dmi->ident);
+               if (!dmi_first_match(find_virtual_pc)) {
+			host->flags |= ATA_HOST_IGNORE_ATA;
+			dev_info(host->dev, "%s detected, ATA device ignore set\n",
+				dmi->ident);
+		}
 	}
 #endif
 }
The patch is not tested and just a concept to fix problem. You can escape the problem with kernel option 'ata_piix.prefer_ms_hyperv=0'.

Ubuntu 12.04(LTS)で、Evernote(WINE上のWindows版)の同期が失敗する(続報)

著者: momokuri Eメール

リンク: http://bugs.winehq.org/show_bug.cgi?id=30598

先日、レポートしたEvernoteがUbuntu12.04で動かないよ、という件だが、その後、OpenSSLの問題だというのは濡れ衣で、OpenSSLが TLS1.1/1.2をサポートするようになったけど、WINEでそのあたりをうまく取り扱っていないことが、問題の発端であることがわかった。

すでに、
http://source.winehq.org/patches/
http://source.winehq.org/patches/data/89343

提案をして、議論しているところだ。
ぜひ、パッチをレビューしたり、さらなる改善を提案したり、動作試験をしたりしてほしい。
http://permalink.gmane.org/gmane.comp.emulators.wine.devel/91356

Ubuntu 12.04(LTS)で、Evernote(WINE上のWindows版)の同期が失敗(fail)する

著者: momokuri Eメール

Ubuntu 12.04(LTS)を導入したら、EvernoteのWindows版をWINEで導入したものが、同期失敗するという事象に遭遇した人も多いと思う。それどころか、さまざまなアプリケーションで、https通信に失敗した、との問題が報告されている。

ここに報告されているとおりだ。

とりあえず、WINEで使っているアプリが動けばいい、という輩には、このパッチをあてれば、幸せになれるでしょう。
i386のプラットホーム上でおこなってください。amd64の64ビットプラットホームでWINEを使っている方も、i386の32bit上でコンパイル必要です。

$ apt-get source wine1.4
$ cd wine1.4-1.4
$ patch -i ../wine-openssl-force-tlsv1.patch
$ sudo apt-get build-dep wine1.4
$ debuild -us -uc -b -i
$ cd ..
$ dpkg -i *.deb

さて、なにが起こっているかというと、httpsをサポートするインターネット上のサーバには、不都合な挙動をしめすものがある、というのが発端です。

httpsでつかうSSL/TLSのバージョンや暗号化方式のネゴシエーションで、クライアントとサーバ間でそれぞれがサポート可能な方式を交換しあいます。その際に、リストのサイズに問題があります。最近の技術の進展で暗号化方法がふえて、リストが大きくなって来ました。

https://bugs.launchpad.net/ubuntu/+source/openssl/+bug/986147

http://www.mentby.com/Group/openssl-users/sslv23method-in-openssl-100.html


+#ifdef OPENSSL_MAX_TLS1_2_CIPHER_LENGTH
+ /* Some servers hang if client hello > 256 bytes
+ * as hack workaround chop number of supported ciphers
+ * to keep it well below this if we use TLS v1.2
+ */
+ if (TLS1_get_version(s) >= TLS1_2_VERSION
+ && i > OPENSSL_MAX_TLS1_2_CIPHER_LENGTH)
+ i = OPENSSL_MAX_TLS1_2_CIPHER_LENGTH & ~1;
+#endif

そこでTLS V1.2のネゴシエーションで、Cipherの長さを制限しよう、ということになったのです。
ところが、これが曲者で、このワークアラウンドがなければ稼働するサーバで、不都合が発生します。

再現も可能で、

openssl s_client -connect www.evernote.com:443

とすればよい。

さて、私のこのパッチだが、WINEへの改変としては、正しくない、変更を加えている。Windowsの挙動と同じなのが正しいとすれば、違反している。それでも、動作するのだ。どうするかというと、SSLv3, SSLv2, TLSv1のネゴシエーションを行うところを、TLSv1のみでネゴシーエションさせる、という改変をくわえている。これで、不具合が実際上はでないのはなぜかというと、すでにSSLv2はセキュリティ上推奨されていない。最近の稼動しているWebサーバであれば、TLSv1をサポートしていないサーバがありえないし、あるとすればメンテナンスされているかどうか、とても心配なので、そんなサービスをつかわなければいいじゃん、というわけだ。

これでなぜ問題が解決するかというと、ネゴシエーションで交換する暗号化方式が制限されているので、リストの長さ制限に対しても問題がないからだ。

この件は、あまり日本語で情報がないようなので、念の為にかいておく。

OpenSSLのメンテなーとしては、1.0.1-4ubuntu4で、この問題は解決ずみ、という立場のようなのだが、Evernoteは引き続き調子悪いようなので、WINE+opensslの挙動としては、引き続き対応が必要、とおもうのである。

Nokia N9で、 3G網でIPv6

著者: momokuri Eメール

IIJにて、LTE網、3G網でのIPv6サポートが開始されている。公式には、LTEの2機種しかサポートしていない。

ところで、いま世の中にあるスマホで、仕様上、3G/LTE経由でIPv6 IPv4のdual stackをサポートできるのは、日本で発売されていないMotorola Droid Bionic for Verizon (Android)と、Nokia N9(Meego)のみらしい。 Droidは、Verizonのロックイン端末であるので、真にオープンでIPv6を携帯通信網でサポート可能なのは、Nokia N9のみということらしい。

ということで、IIJmio高速モバイル/DサービスのSIMカードでできるかな、とおもいたいが、IIJmioはLTE端末のみサポートで、Nokia N9は3G端末なので、結果ネゴシエーションできない。

残念である。以下は、開発用のインタフェースを通じて、Nokia N9の内部に入ってコマンドの出力を取得したもの。

$ ssh 192.168.2.15
Last login: Sat Jun 23 14:00:48 2012 from 192.168.2.14


BusyBox v1.20.0.git (MeeGo 3:1.20-0.1+0m7) built-in shell (ash)
Enter 'help' for a list of built-in commands.

$ uname -a
Linux RM696 2.6.32.48-dfl61-20115101 #1 PREEMPT Thu Dec 22 14:43:29 EET 2011 armv7l GNU/Linux

$ ip addr show

89: gprs0: <POINTOPOINT,NOARP,UP,LOWER_UP> mtu 1400 qdisc pfifo_fast state UNKNOWN qlen 100
link/[821]
inet 10.197.29.242/32 scope global gprs0

これ、無線LANであれば、ちゃんとIPv6が使えている。

3: wlan0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP qlen 1000
link/ether 04:5a:95:a6:aa:aa brd ff:ff:ff:ff:ff:ff
inet 192.168.1.7/24 brd 192.168.1.255 scope global wlan0
inet6 2409:10:8200:0:65a:95ff:fea6:aaaa/64 scope global dynamic
valid_lft 14388sec preferred_lft 12588sec
inet6 fe80::65a:95ff:fea6:aaaa/64 scope link
valid_lft forever preferred_lft forever

これは、Nokia N9のサポートは、IPv4 PDPとIPv6 PDPをそれぞれに有効にしようとするもので、IIJmioはIPv4v6 PDPだというのもあるのかもしれない。

Linux Kernelの208.5日でリブート等する問題

著者: H.Miura Eメール

リンク: http://kenichiokuyama.blogspot.com/2011/12/schedclock-overflow-after-2085-days-in.html

"okkyの銀河制圧奇譚"で、Linux Kernelのスケジューラで使用するTSCをns単位に換算するルーチンでの掛け算オーバーフローが起因して、リブートする等の問題があこることの議論がされている。

しかし、問題が発現していない環境もあって、現象の理解が必要だとおもわれた。ブログ上でのコメントでのレポートでは、656日稼動しているという。

こういうときには、実験的に確認するのがよい。

#include<stdio.h>

static __inline__ unsigned long long rdtsc(void)
{
unsigned hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

int main(){

unsigned long long tick, result;
unsigned long cyc2ns;
unsigned long cpu_khz = 1770000;

tick = rdtsc();
printf("TSC= %llu\n", tick);
cyc2ns = 1000000 * (1 << 10)  /  cpu_khz;
printf("SC= %lu\n", cyc2ns);
result = tick * cyc2ns;
printf("MULT= %llu\n", result);
printf("OVER> %llu\n",  ((unsigned long long) 1 << 63));
}

問題のルーティンに似せた、簡単なこのようなコードを書き、現象の理解をおこなう。 とりあえず、実行したカーネルは、Ubnutu 11.10上の3.0.0である。

miurahr@miurahr-note:~$ ./a.out
TSC= 18906864235232
SC= 578
MULT= 10928167527964096
OVER> 9223372036854775808
miurahr@miurahr-note:~$ ./a.out
TSC= 27953476532
SC= 578
MULT= 16157109435496
OVER> 9223372036854775808

この2つの実行の間に、実行されたPCはスリープされている。このスリープのresume時にcyc2ns_offsetを再計算するようにされている。

上記の結果からわかるように、64bitのTSCが折り返されて、小さくなっている。もちろん、複数CPUが搭載されているので、かならずしも同じCPUの値を取得しているとは言えないのである。とはいえ、得られたヒントは大きい。

static inline unsigned long long __cycles_2_ns(unsigned long long cyc)
{
int cpu = smp_processor_id();
unsigned long long ns = per_cpu(cyc2ns_offset, cpu);
ns += cyc * per_cpu(cyc2ns, cpu) >> CYC2NS_SCALE_FACTOR;
return ns;
}

当該コード部分に注目すると、cyc2ns_offsetに、指摘されている演算結果を加えるコードになっている。どういうことか。ノートPCはとくに、使用時間をのばすために、CPUの速度を動的に変更して、負荷の低い時のCPUの消費電力を削減する。こうすると、当然クロックあたりの時間幅、上記のcyc2nsの値が変化する。したがって、単純にTSCの累計にそのときのCPU速度で計算してしまっては、正しい値になりえない。

で、どうするかというと、CPU速度の変化をさせる時に、そのときの経過時刻をns単位でもとめ、変更後の速度で計算した場合の累計時刻との差分をcyc2ns_offsetに格納する。

1 2 3 4 5 6 7 8 9 10 11 ... 52 >>