Towards Faster Ruby Hash Tables

Hash tables are an important part of dynamic programming languages. They are widely used because of their flexibility, and their performance is important for the overall performance of numerous programs. Ruby is not an exception. In brief, Ruby hash tables provide the following API:

  • insert an element with given key if it is not yet on the table or update the element value if it is on the table
  • delete an element with given key from the table
  • get the value of an element with given key if it is in the table
  • the shift operation (remove the earliest element inserted into the table)
  • traverse elements in their inclusion order, call a given function and depending on its return value, stop traversing or delete the current element and continue traversing
  • get the first N or all keys or values of elements in the table as an array
  • copy the table
  • clear the table

Since Ruby 1.9, traversing hash tables and shift operation should be done in the order elements were included. In other words, elements included earlier should be traversed first. The current implementation of Ruby hash tables is based on an old package written by Peter Moore, with modern murmurhash and siphash algorithms used for hashing Ruby values.

Moore’s original implementation has been changed a lot and the current Ruby hash tables have the following organization:

The typical Ruby hash table (very small hash tables have a different organization) has an array of bins, each bin containing a pointer to a list of table elements (entries, in the Ruby hash table terminology). The calculated hash is translated into the table bin by a modulo operation, which is actually a mask operation as the bin array is of the size of a power of 2.

As you can see, entries have 3 pointers: two for a doubly linked list of entries in their order of inclusion and one for a list of entries corresponding the same bin (in other words, for colliding entries). Using a single linked list for collisions saves memory but makes deleting arbitrary entries during traversal, not a trivial task. So the actual Ruby hash table API is even more complicated than what I described.

When a Ruby hash table’s load factor becomes too big, a new, larger bin array is created.

Modern processors have several levels of cache. Usually, the CPU reads one or a few lines of the cache from memory (or another level of cache). So CPU is much faster at reading data stored close to each other. The current implementation of Ruby hash tables does not fit well with modern processor cache organization, which requires better data locality for faster program speed.

So, how can we improve data locality?

First, we can remove the collision lists by switching to an open addressing hash table where each bin corresponds at most to one entry. Although open addressing needs more bins than the original separate chaining hash tables, we can afford this as we remove one pointer by switching to open addressing. As a result of this switch, we improve data locality for processing entries by their key.

The tendency has been to move from chaining hash tables to open addressing hash tables due to their better fit to modern CPU memory organizations. CPython recently made this switch. GCC has widely-used such hash tables internally for more than 15 years.

To improve data locality for processing entries by their inclusion order, we can remove the doubly linked list and put the entries into an array. It also removes two pointers, and the new entry becomes exactly two times smaller than the original one. That also decreases entry footprint and increases data locality. Removing the lists lets us avoid pointer chasing, a common problem that produces bad data locality.

So our proposed Ruby hash table has the following organization:

The entry array contains table entries in the same order as they were inserted. When the first entry is deleted, a variable containing the index of the current first entry (start) is incremented. In all other cases of deletion, we just mark the entry as deleted by using a reserved hash value.

Bins provide access to entries by their keys. The key hash is mapped to a bin containing the index of the corresponding entry in the entry array (using an index instead of a pointer can be memory saving when we use 8-, 16- or 32-bit indices for reasonable size tables on 64-bit machines).

The size of the array bin is always a power of two, which it makes mapping very fast by using the corresponding lower bits of the hash. Generally, it is not a good idea to ignore some part of the hash. But the alternative approach is worse. For example, we could use a modulo operation for mapping and a prime number for the size of bin array. Unfortunately, the modulo operation for large 64-bit numbers is extremely slow (it takes more 100 cycles on modern Intel CPUs).

Still, the remaining bits of the hash value can be used when the mapping results in a collision. That is also an improvement in comparison with the original tables. We use a secondary hash value function analogous to one in the new CPython hash table implementation. The secondary hash value function is a function of the collision bin index and original hash value. This choice of function guarantees that we can traverse all bins and finally find the corresponding bin, as after several iterations the function becomes X_next = (5 * X_prev + 1) mod pow_of_2, which is a full cycle linear congruential generator since it satisfies the requirements of the Hull-Dobell theorem. By the way, I suspect that the function lookdict in CPython might cycle in extremely rare cases, as X_prev in the function can be more than the size of the table.

When an entry is removed from the table, besides marking the slot as deleted using a special hash value, we also mark the bin by a special value in order to find entries, which had a collision with the removed entries.

There are two reserved values for bins. One denotes an empty bin, while the other one denotes a bin containing a deleted entry.

The length of the bin array is always twice the entry array length. This maintains a healthy table load factor. To improve table memory footprint, we use 8, 16, 32-bits indices on a 64-bit system for smaller tables. As bins are a smaller part of the all table footprint for small tables, we could even increase the bin array two times to decrease the load factor and the collision number even more. But currently, this approach is not used.

The trigger of rebuilding the table is always the case when we cannot insert an entry at the end of the entry array. As opposed to the original hash tables, new arrays can be smaller after rebuilding. This can happen when we remove a lot of entries.

Table rebuilding is done by creating new array entries and bins of appropriate size. We could try to reuse the arrays in some cases by moving non-deleted entries to the start of the array. But this makes little sense, as the most expensive part is entry moves and such an approach just complicates the implementation.

Analysis of the hash table usage in Ruby on Rails done by Koichi Sasada shows that the majority of hash tables are small. We prevent allocations of bins and use a linear search for very small tables less than 5 entries. It saves memory and makes an access to the entries by keys faster for such small tables by saving time to maintain and work with data in the bins.

The original Ruby hash tables use the same approach for tables of less than 7 entries but the implementation is more complicated as it needs a different table representation.

Here is the performance comparison of original and proposed hash tables on 27 MRI hash table benchmarks. We use two major targets for this: x86-64 and ARM.

The average performance improvement on Intel Haswell for the proposed hash tables is about 46%. On ARM, it is even bigger 59%. The proposed implementation also consumes less memory in average than the old one. The below graph shows memory consumption in bytes on x86-64 depending on the number of entries in the hash table.

The proposed implementation is also more straightforward. It permits to simplify the Ruby hash table API in future by avoiding of the original hash tables’ problems with deleting entries during traversal.

Although the new design seems simple, achieving acceptable results required a lot of testing of different variants of the implementation. That is how performance work is usually done.

As an example of such work, one variant of the new hash table implementation had a faster solution to solve the problem of possible denial attacks based on hash collisions:

  • When a new table entry was inserted, we just counted collisions with entries with the same hash (more accurately a part of the hash) but different keys and when some threshold was achieved, we rebuilt the table and started to use a crypto-level hash function. In reality, the crypto-level function would be never used until someone really tries to do the denial attack.
  • Such approach permitted to use faster non-crypto level hash functions in the majority of cases. It also would permit easily to switch to the usage of other slower crypto-level functions (without losing speed in real world scenario), e.g. sha-2 or sha-3. The cryptographic function siphash currently used in MRI is pretty a new function and it is not time-tested yet as older functions.

Although it is not documented, Ruby function hash should be the same as hash function used inside the hash tables and its value should be always the same for an object during one MRI run. Therefore, this approach did not survive the final variant of the hash tables.

It took 8 months from submitting the initial code to committing it into MRI repository (please see issue 12142). Now the new hash table implementation is a part of MRI 2.4.

The hash table implementation discussion contains more 170 posts. Reading the posts can be quite educative and can be a good case of studying open source development aspects and issues.

On a side note, I’d like to thank my managers for permission to invest part of my time to work on Ruby performance in addition to my major responsibilities.


 


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 

Adding buffer overflow detection to string functions

This article describes the steps required to add buffer overflow protection to string functions. As a real-world example, we use the strlcpy function, which is implemented in the libbsd library on some GNU/Linux systems.

This kind of buffer overflow protection uses a GNU Compiler Collection (GCC) feature for array size tracking (“source fortification”), accessed through the __builtin_object_size GCC built-in function. In general, these checks are added in a size-checking wrapper function around the original (wrapped) function, which is strlcpy in our example.

Continue reading “Adding buffer overflow detection to string functions”


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 

Container Images Compliance – what we built at ManageIQ to remove a security pain point – part 2

Part 2 of 2

In part one of this blog post, we mentioned a pain point in Container based environments. We introduced SCAP as a means to measure compliance in computer systems and introduced ManageIQ as a means of automating Cloud & Container based workflows.

Continue reading “Container Images Compliance – what we built at ManageIQ to remove a security pain point – part 2”


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 


For more information about Red Hat OpenShift and other related topics, visit: OpenShift, OpenShift Online.

Container Images Compliance – what we built at ManageIQ to remove a security pain point – part 1

Part 1 of 2

“Docker is about running random crap from the Internet as root on your host”  – Dan Walsh

Continue reading “Container Images Compliance – what we built at ManageIQ to remove a security pain point – part 1”


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 


For more information about Red Hat OpenShift and other related topics, visit: OpenShift, OpenShift Online.

End To End Encryption With OpenShift Part 1: Two-Way SSL

This is the first part of a 2 part article, part 2 (End To End Encryption With OpenShift Part 2: Re-encryption) will be authored by Matyas Danter, Sr Consultant with Red Hat, it will be published soon.

This article aims to demonstrate use cases for Openshift routes to achieve end-to-end encryption. This is a desirable and sometimes mandated configuration for many verticals, which deal with strict regulations.

Continue reading “End To End Encryption With OpenShift Part 1: Two-Way SSL”


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 

Take advantage of your Red Hat Developers membership and download RHEL today at no cost.


For more information about Red Hat OpenShift and other related topics, visit: OpenShift, OpenShift Online.

Migrating my iptables setup to nftables

Wanting to become familiar with nftables, I decided to jump in at the deep end and just use it on my local workstation. The goal was to replace the existing iptables setup, ideally without any drawbacks. The following essay will guide you through what I have done in order to achieve that.

Continue reading “Migrating my iptables setup to nftables”


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 

Securing Fuse 6.3 Fabric Cluster Management Console with SSL/TLS

Introduction

Enabling SSL/TLS in a Fabric is slightly more complex than securing a jetty in a standalone Karaf container. In the following article, we are providing feedback on the overall process. For clarity and simplification, the article will be divided into two parts.

 

Part1: The Management Console

Part2: Securing Web Service:including gateway-http

 

For the purpose of this PoC, the following environment will be used.

Continue reading “Securing Fuse 6.3 Fabric Cluster Management Console with SSL/TLS”


Download and learn more about Red Hat JBoss Fuse, an innovative modular, cloud-ready architecture, powerful management and automation, and world class developer productivity. It is Java™ EE 7 certified and features powerful, enterprise-grade features such as high availability clustering, distributed caching, messaging, transactions, and a full web services stack.


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 

What is mobile security? What is the mobile security ecosystem?

I was recently introduced to a published draft by the National Institute of Standards and Technology (NIST) from the U.S. Department of Commerce which talks about assessing the threats to mobile devices & infrastructure. The document discusses the Mobile Threat Catalogue which describes, identifies and structures the threats posed to mobile information systems.   This blog summarizes the 50-page document with added context and commentary based on my experience in the mobile industry helping organizations building mobile apps.

More than ever before in today’s connected world, the security and protection of our information has the highest priority. Recent Distributed Denial of Service (DDoS) attacks that brought down the internet were generated with the unauthorized use of the Internet of Things (IoT) devices, proving yet again that security breaches can be crippling. The use of mobile devices continues to grow globally and most organizations now have mobile apps that access mission critical information.   It is then important to have a broader view of the entire mobile security ecosystem and understand everything that involves mobile security. As they say, “information is the most powerful weapon”  – in this case to protect our mobile solutions.

The NIST document outlines a catalog of threats to mobile devices and associated mobile infrastructure to support development and implementation of mobile security solutions to better protect enterprise information technology (IT). Smartphones and tablets running modern mobile operating systems are the primary targets in this analysis, not IoT devices.

Mobile devices contain integrated hardware components to support a variety of I/O mechanisms and while some of the communication mechanisms are wireless (i.e., cellular, WiFi, Bluetooth, GPS, NFC), they also include physical connectors (i.e., power and synchronization cable, SD cards, SIM cards, etc.). Wireless and wired device communication mechanisms expose the mobile device to a distinct set of threats and must be secured or the overall security of the device or app may be compromised.  [1]

What do we secure?

Since mobile devices can store a lot of data, personal and enterprise data becomes a target, from sensitive information like home address, telephone number, medical information and credit card numbers to authentication information (users & passwords).   Protecting data also means protecting identity as identity theft can be used to gain unauthorized access to information that can then be compromised or stolen.

Mobile Security Ecosystem

Here the Mobile Security Ecosystem relates to general threat categories that need to be reviewed and understood.

Threats to mobile apps can be classified in 2 groups:

  1. Software vulnerabilities to exploit data residing within the mobile app running on the mobile operating system, and
  2. Malicious or privacy-invasive apps that identify malware based threats to damage your device and/or mobile service.

There are different types of authentication mechanisms for mobile apps; authentication access to devices, to remote services, to remote networks, and to enterprise systems. Vulnerabilities in the mobile apps represent a very high risk of compromising sensitive personal or enterprise data. In summary,  mobile app security is about data protection in the mobile app itself.  

Checklist for Securing Mobile Applications

While building mobile apps, the architecture, and design of the app becomes a critical first step for security,  decisions need to be made and best practices need to be followed.  

Here’s a checklist of considerations for the architecture design.

  • Data transfer encryption
  • Data-at-Rest encryption
  • Store on device and/or store on the cloud
  • Data input validation
  • Use of tokens or keys
  • Hashing and salting passwords
  • Authentication and corporate Identity Management Integration
  • Security policies with an Enterprise Mobility Management system (EMM)
  • Need for VPN connectivity
  • Backend integrations (legacy, web services, RESTful APIs, etc.), use only the data you need, do not transfer everything
  • Secure storage in the cloud and on-premise
  • Files permissions
  • Log files and auditing information
  • Plan for penetration tests
  • Government or regulatory compliance
  • Choice of Mobile Application Development Platform features

More information about mobile app development security best practices by major players in the space:

Enterprise Mobility Management

EMM systems are a common way of managing employee mobile devices in an enterprise. They include a combination of mobile device management (MDM) and mobile application management (MAM) functionality. MDM focuses securing and monitoring mobile devices, while MAM focuses on app distribution and controlling user access to apps. The key feature for EMM systems is to deliver mobile policies, such as only allowing a whitelisted set of applications to run, remote data wipe, ensuring a lock screen and disabling certain device peripherals (e.g., camera).  Different vendors offer different sets of policies, it is important to compare and review differences.  These are implemented via SDKs developers have to use while building apps or by a “wrapper” mechanism on built mobile app binaries.

Other sources of vulnerabilities in the mobile ecosystem

Mobile Operating Systems

Vulnerabilities found at mobile operating systems level which are typically addressed by the platform vendors in a form of patch or new release (Android, iOS, Windows). An example of vulnerabilities is Android 2.3 Gingerbread which is no longer supported by Google and has been considered one of the mobile operating system versions with the most malware attacks.

Device Drivers

Plugins provide access to device hardware and other peripheral device functionality that is ordinarily unavailable to web-based apps (i.e.. camera, geolocation, device motion, accelerometer, vibration, battery status).  Apache Cordova plugins are an example of mobile apps using device functionality and a potential security risk, especially when developers create their own plugins or identify a vulnerability on Cordova. Just like the mobile operating systems, Cordova, and similar products report and address security issue, for example, a critical issue identify on Apache Cordova for Android 4.0.2 and 3.7.2 releases.

SD Cards

SD cards are removable memory used to expand the storage capacity of mobile devices to store data such as photos, videos, music, and application data. Similar other media devices in the Laptop/Desktop world,  SD cards can be source of malware and spyware.

SIM Card

This removable hardware is a chip housing the International mobile subscriber identity (IMSI) needed to obtain access to cellular networks, pre-shared cryptographic keys,  the phone number and even contact information.  Every mobile device has a SIM card (3G & 4G) making it the most widely used security token in the world,  still hackers can send properly signed binary SMS (text messages), which downloads Java applets onto the SIM that can access phone number and identity information.  Use of modern SIM cards with the latest cryptography an SMS firewall for selection of binary SMS to trust are recommended to secure SIM Cards.

Mobile carrier infrastructure and interoperability

This relates to the Mobile Operator and includes threats to the base stations, network backhaul, cellular network cores and signaling threats associated with the widely used Signaling System No. 7 (SS7) networks in the mobile networks.  With 4 Generation (4G) mobile networks the move from proprietary networks and protocols to IP-based networks brought a lot of changes, many of the positive from the operation side, but at the same time brought new security risks never seen by Mobile Operators.    There is not much either a mobile app developer or an organization can do at the network infrastructure level to tackle such vulnerabilities, but it is important to be aware of the risks at infrastructure and interoperability level.

There are many more details, a lot more things to learn with regards to mobile app security, an understanding of the ecosystem and the security threats is a good first step to take on building your secured mobile solutions.

[1] http://csrc.nist.gov/publications/drafts/nistir-8144/nistir8144_draft.pdf

Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 

What comes after 'iptables'? Its successor, of course: `nftables`

Nftables is a new packet classification framework that aims to replace the existing iptables, ip6tables, arptables and ebtables facilities. It aims to resolve a lot of limitations that exist in the venerable ip/ip6tables tools. The most notable capabilities that nftables offers over the old iptables are:

Performance:

  • Support for lookup tables – no linear rule evaluation required
  • No longer enforces overhead of implicit rule counters and address/interface matching

Usability:

  • Transactional rule updates – all rules are applied atomically
  • Applications can subscribe to nfnetlink notifications to receive rule updates when new rules get added or removed
  • nft command-line tool can display a live-log of rules that are being matched for easier ruleset debugging

Continue reading “What comes after 'iptables'? Its successor, of course: `nftables`”


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 

Take advantage of your Red Hat Developers membership and download RHEL today at no cost.

Understanding OpenShift Security Context Constraints

OpenShift gives its administrators the ability to manage a set of security context constraints (SCCs) for limiting and securing their cluster. Security context constraints allow administrators to control permissions for pods using the CLI.

SCCs allow an administrator to control the following:

  1. Running of privileged containers.
  2. Capabilities a container can request to be added.
  3. Use of host directories as volumes.
  4. The SELinux context of the container.
  5. The user ID.
  6. The use of host namespaces and networking.
  7. Allocating an ‘FSGroup’ that owns the pod’s volumes
  8. Configuring allowable supplemental groups
  9. Requiring the use of a read only root file system
  10. Controlling the usage of volume types
  11. Configuring allowable seccomp profiles

Continue reading “Understanding OpenShift Security Context Constraints”


Join Red Hat Developers, a developer program for you to learn, share, and code faster – and get access to Red Hat software for your development.  The developer program and software are both free!

 


For more information about Red Hat OpenShift and other related topics, visit: OpenShift, OpenShift Online.