Tuesday, October 20, 2015

Easy to maintain logic(?) vs speed

Read this blog post about the FizzBuzz problem:

Write a program which return "fizz" if number is multiplier of 3, return "buzz" if its multiplier of 5 and return "fizzbuzz" if number is divisible by both 3 and 5. If number is not divisible by either 3 or 5 then it should just return the number itself

Here are some implementations and test codes:

I personally prefer the implementation of doFizzBuzz1: the logic captures the sense of "if the number is dividable by x, append y to the result".  It makes future modification of adding similar logic easier without understanding the existing code. (e.g. say adding "print 'buzzbazz' if the number is divisible by 10 and 'fizzbuzzbazz' if divisible by 30" etc).

But of course, it is going to be slower as it involves creation of additional objects.  But by how much?  Here are some test results of running the three implementations against the whole range of integer:

Time taken to run net.clarenceho.test.TestFizzBuzz$$Lambda$1/1212899836@75a1cd57 is 175.717783485s
Time taken to run net.clarenceho.test.TestFizzBuzz$$Lambda$2/1285044316@3d012ddd is 141.0544738s
Time taken to run net.clarenceho.test.TestFizzBuzz$$Lambda$3/1607460018@6f2b958e is 140.644691232s

So it is about 25% slower.  Is it worth it? Probably not in this trivial case.  But worth to consider if the logic is complicated and expected to change / enhance in the future.

doFizzBuzz3 is cleaner without nested conditions and runs slightly faster possibly due to fewer branching.

JUnit code used to test the implementations.  Also a good exercise to practice Java lambda and parallel streams.  Tests done on AMD X4 925.

Monday, October 12, 2015

UDOO Quad network driver issue

My UDOO board is running Arch Linux.  Since kernl 4.2.0, it failed to load the network driver.  Found similar issue being discussed and seems that it is related to the Micrel PHY module.

Issue posted to Arch Linux forum.  Kernel output of 4.2.3:

 [  14.797299] Unable to handle kernel NULL pointer dereference at virtual address 000001f5  
 [  14.805442] pgd = ed460000  
 [  14.808196] [000001f5] *pgd=00000000  
 [  14.811821] Internal error: Oops: 5 [#1] SMP ARM  
 [  14.816445] Modules linked in: ppp_async arc4 rt2800usb rt2x00usb rt2800lib rt2x00lib mac80211 cfg80211 crc_ccitt rfkill imx_ipuv3_crtc imx_ipu_v3 dw_hdmi_imx dw_hdmi uio_pdrv_genirq uio imxdrm drm_kms_helper sch_fq_codel ppp_generic slhc ip_tables x_tables  
 [  14.839599] CPU: 2 PID: 240 Comm: systemd-network Not tainted 4.2.3-1-ARCH #1  
 [  14.846732] Hardware name: Freescale i.MX6 Quad/DualLite (Device Tree)  
 [  14.853268] task: ed3c2080 ti: ed3e6000 task.ti: ed3e6000  
 [  14.858686] PC is at fec_enet_open+0x3d4/0x518  
 [  14.863140] LR is at genphy_suspend+0x54/0x5c  
 [  14.867499] pc : [<c0644f00>]  lr : [<c063ca24>]  psr: 00070013  
 [  14.867499] sp : ed3e7b78 ip : ed3e7ab0 fp : ed3e7bdc  
 [  14.878981] r10: 00000200 r9 : ee366800 r8 : c1136770  
 [  14.884211] r7 : 00000001 r6 : ee5e9d44 r5 : 00000001 r4 : ee5e9800  
 [  14.890744] r3 : 000010f9 r2 : c1036a24 r1 : c103696c r0 : ee5e9800  
 [  14.897272] Flags: nzcv IRQs on FIQs on Mode SVC_32 ISA ARM Segment user  
 [  14.904425] Control: 10c5387d Table: 3d46004a DAC: 00000015  
 [  14.910181] Process systemd-network (pid: 240, stack limit = 0xed3e6220)  
 [  14.916897] Stack: (0xed3e7b78 to 0xed3e8000)  
 [  14.921285] 7b60:                            00000006 00000008  
 [  14.929487] 7b80: ed3e7ba4 ee367000 3206e31c 30383831 652e3030 72656874 0074656e 38383132  
 [  14.937683] 7ba0: 2e303030 65687465 74656e72 0036303a c09fc628 c0644b2c ee5e9800 c09fc628  
 [  14.945880] 7bc0: ee5e9830 00000000 00000008 ed424180 ed3e7bfc ed3e7be0 c0817258 c0644b38  
 [  14.954071] 7be0: ee5e9800 00000001 00001003 00001002 ed3e7c24 ed3e7c00 c0817500 c08171ac  
 [  14.962267] 7c00: ee5e9800 00001002 ee5e9940 c09fc628 00000000 00000008 ed3e7c4c ed3e7c28  
 [  14.970471] 7c20: c08175cc c0817470 ee5e9800 00000000 ed3e7cd4 c09fc628 ed1f7310 00000008  
 [  14.978665] 7c40: ed3e7cb4 ed3e7c50 c0825e50 c08175b0 c08b56a8 c04431a0 c0a6a288 ef7b1990  
 [  14.986860] 7c60: ed3e7c84 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  14.995052] 7c80: 00000000 ed1f7328 ed3e7cb4 ee5e9800 ed1f7300 ed424180 ed424180 00000000  
 [  15.003238] 7ca0: 00000008 00000030 ed3e7d8c ed3e7cb8 c0826d58 c0825b58 ed3e7cc4 00000000  
 [  15.011434] 7cc0: 0000000e ee036800 ed3e7cec ed3e7cd8 c01529b0 00000000 00000000 00000000  
 [  15.019628] 7ce0: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  15.027822] 7d00: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  15.036012] 7d20: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ed1f7320  
 [  15.044211] 7d40: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  
 [  15.052407] 7d60: 00000000 00000000 00000000 00000000 ed3e7d8c 00000024 ed1f7300 00000000  
 [  15.060603] 7d80: ed3e7dcc ed3e7d90 c0827770 c0826c70 ed3e7ddc ed3e7da0 c0174060 c092a00c  
 [  15.068793] 7da0: 00000001 ee001cc0 00000000 ed1f7300 ed424180 c08275c8 ee2e9800 00000000  
 [  15.076988] 7dc0: ed3e7dec ed3e7dd0 c08425c8 c08275d4 ed424180 00000030 ed424180 ee2e9800  
 [  15.085176] 7de0: ed3e7e04 ed3e7df0 c08254c4 c084256c ee251400 00000030 ed3e7e34 ed3e7e08  
 [  15.093369] 7e00: c0841d78 c08254a8 ed3e7ed4 7fffffff 00000008 00000000 ee2e9800 ed424180  
 [  15.101558] 7e20: ed3e7ed4 00000000 ed3e7e9c ed3e7e38 c0842440 c0841c90 ee754630 b6ef7000  
 [  15.109751] 7e40: eeef8000 c0134480 ed3e7e8c ed3e7e58 c0134480 00000000 ed265f00 00000000  
 [  15.117943] 7e60: 000000f0 000000c1 000000c1 00000000 ee754630 ed3e7ed4 ed847340 ed847340  
 [  15.126151] 7e80: 00000010 beeefa64 ed3e6000 00000000 ed3e7eb4 ed3e7ea0 c07fafa0 c0841f04  
 [  15.134346] 7ea0: ed3e7f00 00000000 ed3e7fa4 ed3e7eb8 c07fc20c c07faf68 ed3e7edc 00000000  
 [  15.142540] 7ec0: ed791ec8 00000000 00000000 808ca0e8 00000030 ed3e7f00 00000010 00000001  
 [  15.150735] 7ee0: 00000000 00000000 ed3e7ed4 00000000 00000000 00000000 00000000 c00b7d00  
 [  15.158931] 7f00: 00000010 00000000 00000000 00000000 ed087c00 00000000 40b2ae30 0006422c  
 [  15.167132] 7f20: ffffffff 00000000 03c293d3 00000000 000000f9 ed3e7f88 00000001 808ca080  
 [  15.175339] 7f40: 00000107 c000f664 ed3e6000 00000000 ed3e7f84 ed3e7f60 c00b4474 c00b7c9c  
 [  15.183532] 7f60: 0000000e 00000001 808ca080 00000107 c000f664 beeefa90 00000008 00000000  
 [  15.191713] 7f80: beeefa90 beeefa64 00000010 000000f0 00000122 c000f664 00000000 ed3e7fa8  
 [  15.199907] 7fa0: c000f4c0 c07fc150 beeefa64 00000010 00000003 808ca0e8 00000030 00000000  
 [  15.208096] 7fc0: beeefa64 00000010 000000f0 00000122 017d7840 00000000 808d7198 000000f0  
 [  15.216294] 7fe0: beeefa58 beeefa4c 7f6a0d00 b6e61a18 60030010 00000003 00000000 00000000  
 [  15.224511] [<c0644f00>] (fec_enet_open) from [<c0817258>] (__dev_open+0xb8/0x114)  
 [  15.232100] [<c0817258>] (__dev_open) from [<c0817500>] (__dev_change_flags+0x9c/0x140)  
 [  15.240116] [<c0817500>] (__dev_change_flags) from [<c08175cc>] (dev_change_flags+0x28/0x58)  
 [  15.248572] [<c08175cc>] (dev_change_flags) from [<c0825e50>] (do_setlink+0x304/0x720)  
 [  15.256505] [<c0825e50>] (do_setlink) from [<c0826d58>] (rtnl_setlink+0xf4/0x100)  
 [  15.264005] [<c0826d58>] (rtnl_setlink) from [<c0827770>] (rtnetlink_rcv_msg+0x1a8/0x1bc)  
 [  15.272235] [<c0827770>] (rtnetlink_rcv_msg) from [<c08425c8>] (netlink_rcv_skb+0x68/0xc4)  
 [  15.280537] [<c08425c8>] (netlink_rcv_skb) from [<c08254c4>] (rtnetlink_rcv+0x28/0x34)  
 [  15.288474] [<c08254c4>] (rtnetlink_rcv) from [<c0841d78>] (netlink_unicast+0xf4/0x1a8)  
 [  15.296492] [<c0841d78>] (netlink_unicast) from [<c0842440>] (netlink_sendmsg+0x548/0x560)  
 [  15.304769] [<c0842440>] (netlink_sendmsg) from [<c07fafa0>] (sock_sendmsg+0x44/0x54)  
 [  15.312615] [<c07fafa0>] (sock_sendmsg) from [<c07fc20c>] (SyS_sendto+0xc8/0xec)  
 [  15.320023] [<c07fc20c>] (SyS_sendto) from [<c000f4c0>] (ret_fast_syscall+0x0/0x3c)  
 [  15.327698] Code: 0a00001c ea000038 e59435c8 e1a00004 (e59521f4)  
 [  15.333860] ---[ end trace 194130c04452a6bb ]---  

Wednesday, October 7, 2015

Loophole in Google Cloud Messaging (GCM) topic

When implementing an Android app that uses GCM topic messaging, I found that there is a risk of DoS attack on it.  And seems that Google engineers are aware of it.

A potential attack could render the app not able to receive broadcast messages from servers. The only solution will require developers to release a new version of the app using a new GCM sender ID.

Monday, October 5, 2015

Technical details of the Android app Weather Alert Canada

EDIT: Google has since demised GCM and now Environment Canada has its own app to push notification to mobile devices. This app has been unpublished from the Play store.

In late August 2015, there was a massive wind storm in Metro Vancouver that knocked out power to many people.  I relied on radio and Twitter to get updates but I thought it would be better if I could get notifications directly from Environment Canada.  A quick search on Google Play store turned up void.  And hence I spent some time to implement an Android app.

These are the technical details behind the app.

Getting the data

Meteorological data can be retrieved easily from Environment Canada.  The question is, what data to use?  My initial thought was to parse the forecast files and extract alert messages from there.  However, the forecast data is broken down into many files, each for specific area.  And these files are generated frequently.  As I planned to host the logic on Google App Engine (more on that later), I would like to minimize the network traffic.

Luckily, Environment Canada also provides public weather alerts in CAP format.  The CAP files are categorized by issuing offices.  Inside the file, the affected area is described by polygons and geocodes that are intended to overlap directly on a map.  However, what I needed was to somehow link each affected area to provinces / territories. Good thing is Environment Canada has geo data that can map the area description in CAP to specific provinces.

Push mechanism

A few years ago when I first played with push notification, I tried Amazon SNS.  The advantage is that it supports Google Cloud Messaging (GCM), Apple Push Notification (APN) and many more.  But it turns out that since Oct 2013, GCM also supports iOS devices.  So, to keep it simple this time, the backend utilized GCM to push out notifications.

To be specific, GCM Topic is used as the downstream mechanism to broadcast messages.  It is much simpler than keeping registration id of each device and sending out targeted GCM messages.  The downside is, users cannot request to receive notification on certain areas only (well, technically it can be done with topic subscription too, but that means I need to create lots of GCM topics for different areas...)

Backend logic

Before implementing the server side with App Engine, a quick prototype  was created using Python.  urllib2 is used to fetch CAP files from Environment Canada site. After processing the xml file, GCM messages are pushed out with urllib2 in JSON format.

A script was also created to load mapping between areas and provinces into a database.  DBM was used as the API is simple and made it easy to port to Google Datastore.

Another DBM file was also used to keep track of processed CAP files.

Once the prototype is working, porting it to App Engine was easy.  Cron jobs were defined to pull CAP data periodically.  There are also cron jobs to clean datastore of processed files.

Datastore and memcached

When moving the Python scripts to Google App Engine, the DBM databases were ported to  Datastore. As I intended to use the App Engine free tier, there was a need to keep the I/O low.  Luckily App Engine provides memcache as a free service.  With proper caching (over 98% hit rate), I could keep the datastore utilization as low as 2%  of the daily quota.

Android app

The android app was a shameless clone of the GCM sample application.  On the navigator bar, users can choose to show notifications for specific provinces only.  The main window is a WebView.  A HTML file and some JavaScript are included in the app to fetch Environment Canada WeatherLink.