street programmer

Assignment problem

2020-06-12T21:49:00.003-07:00

https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem-set-1-introduction/

tornado tutorials:

refactoring-tornado-coroutines

2020-05-17T14:29:00.000-07:00

Systemd:

1. overview and cheatsheet
Overview and cheatsheet

mock

2020-04-26T19:09:00.001-07:00

mock

Linux source code

2020-04-03T19:40:00.000-07:00

elixir.bootlin.com

120 sseconds

2020-04-02T21:08:00.002-07:00

120 seconds

120 seconds

SLUB allocation failure

Write a linux kernel module

2020-04-02T05:31:00.000-07:00

How to write a simple linux kernel module

linux perf tool

2020-04-01T12:56:00.002-07:00

linux kernel books

2020-03-30T20:34:00.001-07:00

1. linux memory management

2. linked in direct men reclaim mode

Kernel runs out packet buffers:
1. unload runs out of packet buffers

2. How SKB (Socket Buffer) works.

3. How to resolve packet loss

4. Linux Zone LOW/HIGH/MIN

5. Deep into linux memory management
6.solar flare driver code

how to decode page allocation failure

How to tune the Linux kernel for memory performance

2020-03-29T20:52:00.001-07:00

How to tune the Linux kernel for memory performance:

How to tune the Linux kernel for memory performance

Context

The linux kernel attempts to optimize RAM utilization, in that it occupies unused RAM with caches. This is done on the basis that unused RAM is wasted RAM.
Over time the kernel will fill the RAM with cache. As more memory is required by the applications/buffers, the kernel goes through the cache memory pages and finds a block large enough to fit the requested malloc. It then frees that memory and allocates it to the calling application.
Under some circumstances, this can affect the general performance of the system as cache de-allocation is time-consuming in comparison with access to unused RAM. Higher latency could therefore sometimes be observed.
This latency will purely be based on the fact that RAM is being used to its full speed potential. As such, no other symptoms may occur apart from general overall and potentially sporadic latency increases. The equivalent would be similar to symptoms that may be observed if the hard disks are not keeping up with reads and writes. The latency may also affect either Aerospike, or operating system components, such as network card/iptables/ebtables/iproute2 mallocs. As such this may show network-based latency instead. The following article discusses this further and provides steps to minimize impact on the system.

Explanation

The kernel memory cache contains the following:

dirty cache - Data blocks not yet committed to the file systems which support caching (e.g. ext4). This can be emptied by issuing the sync command athough this may imply a periodic performance penalty. This is not advised for normal usage unless it is extremely important to commit data to hard drive (for example when expecting a failure).
clean cache - Data blocks which are on the hard drive but are also retained in memory for fast access. Dropping the clean cache can result in a performance deficit as all data will read from disk, whereas beforehand, the frequently used data would be fetched directly from RAM.
inode cache - Cache of the inode location information. This can be dropped as with clean cache but with the attendant performance penalty.
slab cache - This type of cache stores objects allocated via malloc by applications so that they may be re-malloc again in the future with object data already populated, resulting in speed gain during memory allocations.

While not much can be done with dirty cache, the other cached objects can be cleared. This has potentially 2 outcomes. Latency in high-malloc applications, such as Aerospike when storing data in memory, will be reduced. On the other hand, disk access may slow down, as all data will have to be read from disk.
Clearing slab cache on a server can potentially introduce a temporary speed penalty (spike). For this reason, it is not advised to clear caches. Instead, it is preferred to inform the system that a certain amount of RAM should never be occupied by cache.
If necessary, clearing the cache can be performed as follows:

# clear page cache (above type 2 and 3)
$ echo 1 > /proc/sys/vm/drop_caches

# clear slab cache (above type 4)
$ echo 2 > /proc/sys/vm/drop_caches

# clear page and slab cache (types 2,3,4)
$ echo 3 > /proc/sys/vm/drop_caches

Most of the space will be occupied by page cache, not slab cache. It is recommended that when clearing cache, to only drop the page cache (echo 1).
For a more permanent fix, a minimum number of free RAM can be set for the kernel. Consider the following example:

Total RAM: 100GB
Used: 10GB
Buffers: 40GB
Minimum free: 10GB
Cache: 40GB

In this example, there is 10GB free memory selected using the minimum free option. In such a case, if 5GB of memory is allocated for buffers, the kernel will allow the allocation to happen instantly. It will then de-allocate some cache to ensure 10GB free memory. Allocations will happen instantly and cache will be dynamically shrunk to ensure that 10GB remains free at all times. The new allocation would look as follows:

Total RAM: 100GB
Used: 10GB
Buffers: 45GB
Minimum free: 10GB
Cache: 35GB

Fine-tuning these parameters is dependant upon the current utilization. For Aerospike, it should be at least 1.1GB free in min_free_kbytes, if the available system memory allows. This means that caches will still operate sufficiently, while leaving a margin for applications to allocate into.

$ cat /proc/sys/vm/min_free_kbytes
67584

Tuning is performed by performing an echo NUMBER > /proc/sys/vm/min_free_kbytes where, NUMBER is the number of kilobytes required to be free in the system. To leave 3% of memory on a 100GB RAM machine unoccupied, the command would be:

echo 3145728 > /proc/sys/vm/min_free_kbytes

Caution should be exercised when setting this parameter, both too low and too high values can have an adverse effect upon system performance. Setting min_free_kbytes too low prevents the system from reclaiming memory. This can result in system hangs and OOM kills of processes.
Setting this parameter to a value that is too high (5-10% of total system memory) will cause the system to run out of memory immediately. Linux is designed to use all available RAM to cache file system data. Setting a high min_free_kbytes value results in the system spending too much time reclaiming memory.
The standard recommendation 131 would be to keep min_free_kbytes at 1-3% of the total memory on the system.
It is advised to either reduce swappiness to 0 or not use swap. For low-latency operations, using swap to any extent will drastically slow down performance.
To set the swappiness to 0 to reduce potential latency:

echo 0 > /proc/sys/vm/swappiness

Notes

IMPORTANT: Any and all changes above are NOT permanent. They only happen during machine runtime. To make the changes permanent, additions must be made to /etc/sysctl.conf.
The following lines make the changes shown above permanent:

vm.min_free_kbytes = 5248000
vm.swappiness = 0

As always, editing such parameters can be destructive if done incorrectly. It is recommended to perform the changes in a lab environment before moving to production. Making changes dynamically before performing permanent change helps in mitigating any potential side effects which could occur.
There is another parameter aimed at a similar output as the above, called zone_reclaim. Unfortunately, this parameter causes aggressive reclaims and scans and should therefore be disabled. This is disabled as standard on all newer kernels and distributions.
The following command can be used to ensure that zone_reclaim is disabled:

$ sysctl -a |grep zone_reclaim_mode
vm.zone_reclaim_mode = 0

Keywords

KERNEL MEMORY CACHE DROP_CACHES MIN_FREE_KBYTES SWAPPINESS

Timestamp

June 2 2019

Linux network stack

2020-03-29T20:48:00.001-07:00

Navigating the Linux kernel network stack: receive path:

Linux networking from ground up

NAPI

linux network illustration

Monitor and tuning linux network

Background

At work we practice continuous integration in terms of performance testing alongside different stages of functional testing.

In order to do this, we have a performance environment that fully replicates the hardware and software used in our production environments. This is necessary in order to be able to find the limits of our system in terms of throughput and latency, and means that we make sure that the environments are identical, right down to the network cables.

Since we like to be ahead of the curve, we are constantly trying to push the boundaries of our system to find out where it will fall over, and the nature of the failure mode.

This involves running production-like load against the system at a much higher rate than we have ever seen in production. We currently aim to be able to handle a constant throughput of 2-5 times the maximum peak throughput ever observed in production. We believe that this will give us enough headroom to handle future capacity requirements.

Our Performance & Capacity team has a constant background task of:

increase load applied to the system until it breaks
find and fix the bottleneck

Using this process, we aim to ensure that we are able to handle spikes in demand, and increases in user numbers, while still achieving a consistent and low latency-profile.

There is actually a third step to this process, which is something like 'buy new hardware' or 'modify the system to do less work', since there is only so much than tuning will buy you.

The code that is inspected in this article is that taken by inbound multicast traffic on Linux kernel version 4.0.

Identifying a bottleneck

During the latest iteration of the break/fix cycle, we identified one particular service as problematic. The service in question is one of those responsible for consuming the output of our matching engine, which can peak at 250,000 messages per second at our current performance-test load.

When we have a bottleneck in one of our services, it usually follows a familiar pattern of back-pressure from the application processing thread, resulting in packets being dropped by the networking card.

In this case however, we could see from our monitoring that we were not suffering from any processing back-pressure, so it was necessary to delve a little deeper into the network packet receive path in order to understand the problem.

Understanding the data flow

Components involved in network packet receipt

The Linux kernel provides a number of counters that can give an indication of any problems in the network stack. Since we are concerned with throughput, we will be most interested in things like queue depths and drop counts.

Before looking at the available statistics, let's take a look at how a packet is handled once it is pulled off the wire.

The journey begins in the network driver code; this is vendor-specific and in the majority of cases open source. In this example, we're working with an Intel 10Gb card, which uses the ixgbe driver. You can find out the driver used by a network interface by using ethtool:

ethtool -i <device-name>

This will generate output that looks something like:

driver: ixgbe
version: 3.19.1-k
firmware-version: 0x546d0001
bus-info: 0000:41:00.0
supports-statistics: yes
supports-test: yes
supports-eeprom-access: yes
supports-register-dump: yes
supports-priv-flags: no

The driver code can be found in the Linux kernel source here.

NAPI

NAPI, or New API is a mechanism introduced into the kernel several years ago. More background can be read here, but in summary, NAPI increases network receive performance by changing packet receipt from interrupt-driven to polling-mode.

Previous to the introduction of NAPI, network cards would typically fire a hardware interrupt for each received packet. Since an interrupt on a CPU will always cause suspension of the executing software, a high interrupt rate can interfere with software performance. NAPI addresses this by exposing a poll method to the kernel, which is periodically executed (actually via an interrupt). While the poll method is executing, receive interrupts for the network device are disabled. The effect of this is that the kernel can drain potentially multiple packets from the network device receive buffer, thus increasing throughput at the same time as reducing the interrupt overhead.

Interrupt handling

When the network device driver is initially configured, it first associates a handler function with the receive interrupt. This function will be invoked whenever the CPU receives a hardware interrupt from the network card.

For the card that we're looking at, this happens in a method called ixgbe_request_msix_irqs:

request_irq(entry->vector, &ixgbe_msix_clean_rings, 0,
   q_vector->name, q_vector);

So when an interrupt is received by the CPU, the ixgbe_msix_clean_rings method simply schedules a NAPI poll, and returns IRQ_HANDLED:

static irqreturn_t ixgbe_msix_clean_rings(int irq, void *data)
{
    struct ixgbe_q_vector *q_vector = data;
    ...
    if (q_vector->rx.ring || q_vector->tx.ring)
        napi_schedule(&q_vector->napi);

    return IRQ_HANDLED;
}

Scheduling the NAPI poll entails adding some work to the per-cpu poll list maintained in the softnet_data structure:

static inline void ____napi_schedule(struct softnet_data *sd,
                                     struct napi_struct *napi)
{
    list_add_tail(&napi->poll_list, &sd->poll_list);
    __raise_softirq_irqoff(NET_RX_SOFTIRQ);
}

and then raising a softirq event. Once the softirq event has been raised, the driver knows that the poll function will be called in the near future.

softirq processing

For more background on interrupt handling, the Linux Device Drivers book has a chapter dedicated to this topic. Suffice to say, doing work inside of a hardware interrupt context is generally avoided within the kernel; while handling a hardware interrupt a CPU is not executing user or kernel software threads, and no other hardware interrupts can be handled until the current routine is complete. One mechanism for dealing with this is to use softirqs.

Each CPU in the system has a bound process called ksoftirqd/<cpu_number>, which is responsible for processing softirqevents.

In this manner, when a hardware interrupt is received, the driver raises a softIRQ to be processed on the ksoftirqd process. So it is this process that will be responsible for calling the driver's poll method.

The softirq handler net_rx_action is configured for network packet receive events during device initialisation. All softirqevents of type NET_RX_SOFTIRQ will be handled by the net_rx_action function.

So, having followed the code this far, we can say that when a network packet is in the device's receive ring-buffer, the net_rx_action function will be the top-level entry point for packet processing.

net_rx_action

At this point, it is instructive to look at a function trace of the ksoftirqd process. This trace was generated using ftrace, and gives a high-level overview of the functions involved in processing the available packets on the network device.

net_rx_action() {
  ixgbe_poll() {
    ixgbe_clean_tx_irq();
    ixgbe_clean_rx_irq() {
      ixgbe_fetch_rx_buffer() {
        ... // allocate buffer for packet
      } // returns the buffer containing packet data
      ... // housekeeping
      napi_gro_receive() {
        // generic receive offload
        dev_gro_receive() {
          inet_gro_receive() {
            udp4_gro_receive() {
              udp_gro_receive();
            }
          }
        }
        netif_receive_skb_internal() {
          __netif_receive_skb() {
            __netif_receive_skb_core() {
              ...
              ip_rcv() {
                ...
                ip_rcv_finish() {
                  ...
                  ip_local_deliver() {
                    ip_local_deliver_finish() {
                      raw_local_deliver();
                      udp_rcv() {
                        __udp4_lib_rcv() {
                          __udp4_lib_mcast_deliver() {
                            ...
                            // clone skb & deliver
                            flush_stack() {
                              udp_queue_rcv_skb() {
                                ... // data preparation
                                // deliver UDP packet
                                // check if buffer is full
                                __udp_queue_rcv_skb() {
                                  // deliver to socket queue
                                  // check for delivery error
                                  sock_queue_rcv_skb() {
                                    ...
                                    _raw_spin_lock_irqsave();
                                    // enqueue packet to socket buffer list
                                    _raw_spin_unlock_irqrestore();
                                    // wake up listeners
                                    sock_def_readable() {
                                      __wake_up_sync_key() {
                                        _raw_spin_lock_irqsave();
                                        __wake_up_common() {
                                          ep_poll_callback() {
                                            ...
                                            _raw_spin_unlock_irqrestore();
                                          }
                                        }
                                        _raw_spin_unlock_irqrestore();
                                      }
...

The softirq handler performs the following steps:

Call the driver's poll method (in this case ixgbe_poll)
Perform some GRO functions to group packets together into a larger work unit
Call the packet type's handler function (ip_rcv) to walk down the protocol chain
Parse IP headers, perform checksumming then call ip_rcv_finish
The buffer's destination function is invoked, in this case udp_rcv
Since these are multicast packets, __udp4_lib_mcast_deliver is called
The packet is copied and delivered to each registered UDP socket queue
In udp_queue_rcv_skb, buffers are checked and if space remains, the skb is added to the end of the socket's queue

Monitoring back-pressure

When attempting to increase the throughput of an application, we need to understand where back-pressure is coming from.

At this point in the data receive path, we could have throughput issues for two reasons:

The softirq handling mechanism cannot dequeue packets from the network device fast enough
The application processing the destination socket is not dequeuing packets from the socket buffer fast enough

softirq back-pressure

For the first case, we need to look at softnet stats (/proc/net/softnet_stat), which are maintained by the network receive stack.

The softnet stats are defined here as the per-cpu struct softnet_data, which contains a few fields of interest: processed, time_squeeze and dropped.

processed is the total number of packets processed, so is a good indicator of total throughput.

time_squeeze is updated if the ksoftirq process cannot process all packets available in the network device ring-buffer before its cpu-time is up. The process is limited to 2 jiffies of processing time, or a certain amount of 'work'.

There are a couple of sysctls that control these parameters:

net.core.netdev_budget - the total amount of processing to be done in one invocation of net_rx_action
net.core.dev_weight - an indicator to the network driver of how much work to do per invocation of its napi poll method

The ksoftirq daemon will continue to call napi_poll until either the time has run out, or the amount of work reported as completed by the driver exceeds the value of net.core.netdev_budget.

This behaviour will be driver-specific; in the Intel 10Gb driver, completed work will always be reported as net.core.dev_weight if there are still packets to be processed at the end of a poll invocation.

Given some example numbers, we can determine how many times the napi_poll function will be called for a softIRQ event:

net.core.netdev_budget = 300
net.core.dev_weight = 64

poll_count = (300 / 64) + 1 => 5

If there are still packets to be processed in the network device ring-buffer, then the time_squeeze counter will be incremented for the given CPU.

The dropped counter is only used when the ksoftirq process is attemping to add a packet to the backlog queue of another CPU. This can happen if Receive Packet Steering is enabled, but since we are only looking at UDP multicast without RPS, I won't go into the detail.

So if our kernel helper thread is unable to move packets from the network device receive queue to the socket's receive buffer fast enough, we can expect the time_squeeze column in /proc/net/softnet_stat to increase over time.

In order to interpret the file, it is worth looking at the implementation. Each row represents a CPU-local instance of the softnet_stat struct (starting with CPU0 at the top), and the third column is the time_squeeze entry.

The only tunable that we have at our disposal is the netdev_budget value. Increasing this will allow the ksoftirq process to do more work. The process will still be limited by a total processing time of 2 jiffies though, so there will be an upper ceiling to packet throughput.

Given the speeds that modern processors are capable of, it is unlikely that the ksoftirq daemon will be unable to keep up with the flow of data, if properly configured.

In order to give the kernel the best chance to do so, make sure that there is no contention for CPU resources by assigning network interrupts to a number of cores, and then using isolcpus to make sure that no other processes will be running on them. This will give the ksoftirq daemon the best chance of copying the inbound packets in a timely manner.

If the ksoftirq daemon is squeezed frequently enough, or is just unable to get CPU time, then the network device will be forced to drop packets from the wire. In this case, we can use ethtool to find the rx_missed_errors count:

ethtool -S <device-name> | grep rx_missed
rx_missed_errors: 0

alternatively, the same data can be found by looking at the following file:

/sys/class/net/<device-name>/statistics/rx_missed_errors

For a full description of each of the statistics reported by ethtool, refer to this document.

Application back-pressure

It is far more likely that our user programs will be the bottleneck here, and in order to determine whether that is the case, we need to look at the next stage in the message receipt path. A continuation of this post will explore that area in more detail.

Summary

For UDP-multicast traffic, we have seen in detail the code paths involved in moving an inbound network packet from a network device to a socket's input buffer. This stage can be broadly summarised as follows:

On packet receipt, the network device fires a hardware interrupt to the configured CPU
The hardware interrupt handler schedules a softIRQ on the same CPU
The softIRQ handler thread (ksoftirqd) will disable receive interrupts and poll the card for received data
Data will be copied from the network device's receive buffer into the destination socket's input buffer
After a certain amount of work has been done, or no inbound packets remain, the ksoftirq daemon will re-enable receive interrupts and return

In order to optimise for throughput, there are a couple of things to try tuning:

Increase the amount of work that the ksoftirq daemon is allowed to do (net.core.netdev_budget)
Make sure that the ksoftirq daemon is not contending for CPU resource or being descheduled due to other hardware interrupts
Increase the size of the network device's ring-buffer (ethtool -g <device-name>)

As with all performance-related experiments, never attempt to tune the system without being able to measure the impact of any changes in isolation.

First, make sure that you know what the problem is (i.e. rx_missed_errors or time_squeeze is increasing), the add the relevant monitoring. For this particular case, we would want to be able to correlate the application experiencing message loss with a change in the relevant counters, so recording and charting the numbers would be a good start.

Once this has been done, changes can be made to system configuration to see if an improvement can be made.

Lastly, any changes to the tuning parameters that I've mentioned MUST be configured via automation. We have sadly lost a fair amount of time to manual changes being made on machines that have not persisted across reboots.

It is all too easy (and I speak as a repeat offender) to make adjustments, find the optimal configuration, and then move on to something else. Do yourself and your colleagues a favour and automate configuration management!

Resources

I read lots of really useful documents while learning about this area of the kernel. Here are a few of them:

https://www.coverfire.com/articles/queueing-in-the-linux-network-stack/

https://access.redhat.com/sites/default/files/attachments/20150325_network_performance_tuning.pdf

https://www.kernel.org/doc/Documentation/networking/scaling.txt

https://wiki.openwrt.org/doc/networking/praxis

Navigating the Linux kernel network stack: into user land

This is a continuation of my previous post, in which we follow the path of an inbound multicast packet to the user application.
At the end of the last post, I mentioned that application back-pressure was most likely to be the cause of receiver packet-loss. As we continue through the code path taken by inbound packets up into user-land, we will see the various points at which data will be discarded due to slow application processing, and what metrics can shed light on these events.

Protocol mapping

First of all, let's take a quick look at how a received data packet is matched up to its handler function.
We can see from the stack-trace below that the top-level function calls when dealing with the packets are packet_rcv and ip_rcv:

__netif_receive_skb_core() {
    packet_rcv() {
        skb_push();
        __bpf_prog_run();
        consume_skb();
    }
    bond_handle_frame() {
        bond_3ad_lacpdu_recv();
    }
    packet_rcv() {
        skb_push();
        __bpf_prog_run();
        consume_skb();
    }
    packet_rcv() {
        skb_push();
        __bpf_prog_run();
        consume_skb();
    }
    ip_rcv() {
        ...

This trace captures the part of the receive path where the inbound packet is passed to each registered handler function. In this way, the kernel handles things like VLAN tagging, interface bonding, and packet-capture. Note the __bpf_prog_run function call, which indicates that this is the entry point for pcap packet capture and filtering.

The protocol-to-handler mapping can be viewed in the file /proc/net/ptype:

[pricem@metal]$ cat /proc/net/ptype 
Type Device      Function
ALL  em1      packet_rcv
0800          ip_rcv
0011          llc_rcv [llc]
0004          llc_rcv [llc]
88f5          mrp_rcv [mrp]
0806          arp_rcv
86dd          ipv6_rcv

Comparing against this reference, it is clear that the kernel reads the value of the ethernet frame's EtherType field and dispatches to the corresponding function. There are also some functions that will be executed for all packet types (signified by type ALL).

So our inbound packet will be processed by the capture hooks, even if no packet capture is running (this then must presumably be very cheap), before being passed to the correct protocol handler, in this case ip_rcv.

The socket buffer

As discussed previously, each socket on the system has a receive-side FIFO queue that is written to by the kernel, and read from by the user application.

ip_rcv starts by getting its own copy of the incoming packet, copying if the packet is already shared. If the copy fails due to lack of memory, then the packet is discarded, and the Discard count of the global ip statistics table is incremented. Other checks made at this point include the IP checksum, header-length check and truncation check, each of which update the relevant metrics.

Before calling the ip_rcv_finish function, the packet is diverted through the netfilter module where software-based network filtering can be applied.

Assuming that the packet is not dropped by a filter, ip_rcv_finish passes the packet on to the next protocol-handler in the chain, in this instance, udp_rcv.

In the internals of the udp_rcv function, we finally get to the point of accessing the socket FIFO queue.
Simple validation performed at this point includes packet-length check and checksum. Failure of these checks will cause the relevant statistics to be updated in the global udp statistics table.

Because the traffic we're tracing is multicast, the next handler function is __udp4_lib_mcast_deliver.
With some exotic locking in place, the kernel determines how many different sockets this multicast packet needs to be delivered to. It is worth noting here that there is a smallish number (256 / sizeof( struct sock)) of sockets that can be listening to a given multicast address before the possibility of greater lock-contention creeps in.

An effort is made to enumerate the registered sockets with a lock held, then perform the packet dispatching without a lock. However, if the number of registered sockets exceeds the specified threshold, then packet dispatch (the flush_stack function) will be handled while a lock is held.

Once in flush_stack, the packet is copied for each registered socket, and pushed onto the FIFO queue.
If the kernel is unable to allocate memory in order to copy the buffer, the socket's drop-count will be incremented, along with the RcvBufErrors and InErrors metrics in the global udp statistics table.

After another checksum test, we are finally at the point where socket-buffer overflow is tested:

if (sk_rcvqueues_full(sk, sk->sk_rcvbuf)) {
    UDP_INC_STATS_BH(sock_net(sk), UDP_MIB_RCVBUFERRORS,
                     is_udplite);
    goto drop;
}

If the size of the socket's backlog queue, plus the memory used in the receive queue is greater than the socket receive buffer size, then the RcvBufferErrors and InErrors metrics are updated in the global udp statitics table, along with the socket's drop count.

To safely handle multi-threaded access to the socket buffer, if an application has locked the socket, then the inbound packet will be queued to the socket's backlog queue. The backlog queue will be processed when the lock owner releases the lock.

Otherwise, pending more checks that socket memory limits have not been exceeded, the packet is added to the socket's sk_receive_queue.

Finally, once the packet has been delivered to the socket's receive queue, notification is sent to any interested listeners.

Kernel statistics

Now that we have seen where the various capacity checks are made, we can make some observations in the proc file system.

There are protocol-specific files in /proc/net that are updated by the kernel whenever data is received.

`/proc/net/snmp`

This file contains statistics on multiple protocols, and is the target for updates to the UDP receive buffer errors. So when we want to know about system-wide receive errors, this is the place to look. When this file is read, a function call iterates through the stored values and writes them to the supplied destination. Such is the magic of procfs.

In the output below, we can see that there have been several receive errors (RcvbufErrors), and the number is matched by the InErrors metric:

Udp: InDatagrams NoPorts InErrors OutDatagrams RcvbufErrors SndbufErrors InCsumErrors
Udp: 281604018683 4      261929024 42204463516 261929024    0            0

Each of the columns maps to a constant specified here, so to determine when these values are updated, we simply need to search for the constant name.

There is a subtle difference between InErrors and RcvbufErrors, but in our case when looking for socket buffer overflow, we only care about RcvbufErrors.

`/proc/net/udp`

This file contains socket-specific statistics, which only live for the lifetime of a socket. As we have seen from the code so far, each time the RcvbufErrors metric has been incremented, so too has the corresponding sk_drops value for the target socket.

So if we need to differentiate between drop events on a per-socket basis, this file is what we need to observe. The contents below can be explained by looking at the handler function for socket data:

[pricem@metal ~]# cat /proc/net/udp
sl  local_address rem_address   st tx_queue rx_queue ... inode ref pointer drops
47: 00000000:B87A 00000000:0000 07 00000000:00000000 ...  239982339 2 ffff88052885c440 0     
95: 4104C1EF:38AA 00000000:0000 07 00000000:00000000 ...  239994712 2 ffff8808507ed800 0     
95: BC04C1EF:38AA 00000000:0000 07 00000000:00000000 ...  175113818 2 ffff881054a8b080 0     
95: BE04C1EF:38AA 00000000:0000 07 00000000:00000000 ...  175113817 2 ffff881054a8b440 0     
...

For observing back-pressure, we are interested in the drops column, and the rx_queue column, which is a snapshot of the amount of queued data at the time of reading. Local and remote addresses are hex-encoded ip:port addresses.

Monitoring this file can tell us if our application is falling behind the packet arrival rate (increase in rx_queue), or whether the kernel was unable to copy a packet into the socket buffer due to it already being full (increase in drops).

Tracepoints

If we wish to capture more data about packets that are being dropped, there a three tracepoints that are of interest.

sock:sock_rcvqueue_full: called when the amount of memory already allocated to the socket buffer is greater than or equal to the configured socket buffer size.
sock:sock_exceed_buf_limit: called when the kernel is unable to allocate more memory for the socket buffer.
udp:udp_fail_queue_rcv_skb: called shortly after the sock_rcvqueue_full event trace for the same reason.

These events can be captured using Linux kernel tracing tools such as perf or ftrace.

Summary

Let's just recap the points of interest for monitoring throughput issues in the network receive path.

/proc/net/softnet_stat: contains statistics updated by the ksoftirq daemon. Useful metrics are processed, timesqueeze and dropped (discussed in detail in the last post).
/proc/net/snmp: contains system-wide statistics for IP, TCP, UDP. Useful metrics indicate memory exhaustion, buffer exhaustion, etc.
/proc/net/udp: contains per-socket information. Useful for monitoring queue depths/drops for a particular socket.
/proc/net/dev: contains statistics provided by network devices present on the system. Some supplied statistics are driver-specific.
/sys/class/net/DEV_NAME/statistics: provides more detailed statistics from the network device driver.

min_free_kbytes

2020-03-29T20:08:00.002-07:00

How the Linux kernel divides up your RAM

June 15, 2012

min_free_kbytes cause disk cache fails

The Linux kernel doesn't consider all of your physical RAM to be one great big undifferentiated pool of memory. Instead, it divides it up into a number of different memory regions (at least for kernel purposes), which it calls 'zones' (to simplify slightly). What memory regions there are depends on whether your machine is 32-bit or 64-bit and also how complicated it is.
The zones are:

DMA is the low 16 MBytes of memory. At this point it exists for historical reasons; once upon what is now a long time ago, there was hardware that could only do DMA into this area of physical memory.
DMA32 exists only in 64-bit Linux; it is the low 4 GBytes of memory, more or less. It exists because the transition to large memory 64-bit machines has created a class of hardware that can only do DMA to the low 4 GBytes of memory.(This is where people mutter about everything old being new again.)
Normal is different on 32-bit and 64-bit machines. On 64-bit machines, it is all RAM from 4GB or so on upwards. On 32-bit machines it is all RAM from 16 MB to 896 MB for complex and somewhat historical reasons.Note that this implies that machines with a 64-bit kernel can have very small amounts of Normal memory unless they have significantly more than 4GB of RAM. For example, a 2 GB machine running a 64-bit kernel will have no Normal memory at all while a 4 GB machine will have only a tiny amount of it.
HighMem exists only on 32-bit Linux; it is all RAM above 896 MB, including RAM above 4 GB on sufficiently large machines.

Normally allocations can come from a more restrictive zone than you asked for if that's where the free memory is. For example, if you ask for Normal memory on a 64-bit machine and there isn't any but there's lots of DMA32, you'll get DMA32. It's just that kernel prefers to preserve DMA32 for things that have asked for it specifically.
Now, this is a slight simplification; actually, zones and memory are attached to a 'node'. Ordinary machines have only a single node, node 0, but sufficiently large servers can have multiple nodes (we have one with eight). Nodes are how Linux represents NUMA architectures. To simplify, each CPU is also associated with a node and the kernel will try to allocate memory for a process running on a CPU from that node's RAM, because it is considered 'closest' to that CPU.
I believe that the special zones (DMA, DMA32, and on 32-bit machines, Normal) will only be present on one node, generally node 0. All other nodes will generally have only Normal (on 64-bit kernels) or HighMem (on 32-bit kernels) memory.
You can see a bunch of information about your system's nodes, zones, and the state of their memory in /proc/pagetypeinfo, /proc/zoneinfo, /proc/<pid>/numa_maps, and /proc/buddyinfo, which deserves an explanation of its own.
The kernel's basic unit of allocatable memory is the 4 KByte page (many stats are reported by page count, instead of memory size in Kbytes). The kernel also keeps track of larger contiguous blocks of pages because sometimes kernel code wants, say, a contiguous 64 kbyte block of memory. /proc/buddyinfo shows you how many such free chunks there are for each allocation 'order'. The 'order' is 2^order pages, ie order 0 is a single page, order 1 is 2 pages (8 KB), order 2 is 4 pages (16 Kb), and so on.
So when /proc/buddyinfo reports, for example:

Node 0, zone DMA32 7 20 2 4 6 4 3 4 6 5 369

This means that in the DMA32 zone on this machine there are currently 7 free solo 4kb pages, 20 8kb two-page chunks, 2 16kb chunks, and so on, all the way up to 369 1024-page (4 Mbyte) chunks. Since the kernel will split larger chunks to get smaller ones if it needs to, the DMA32 zone on this machine is in pretty good shape despite seeming to not have many order 0 4kb pages available.
(This is also what /proc/pagetypeinfo means by 'order' in its output.)
In fact, having a disproportionate number of order 0 pages free is generally a danger sign since order 0 pages exist only when the kernel can't merge them together to form higher-order free chunks. Lots of order 0 pages thus mean lots of fragmentation, where the kernel can't even find two adjacent aligned pages to merge into an 8kb order 1 chunk.

linux mem management

NFS hang, sk_drops increasing, segs_in not, pfmemalloc suspected

Code change PR

play with disk cache

kernel run out men and disk cache

network stack continous mem

low min_free_kbytes can cause cache reclaim failure

Increase min_free_kbytes to 4GB

memory zone's min/low/high graph

2019-12-16T07:36:00.002-08:00

python links:

c++ links:

2019-10-26T20:36:00.000-07:00

python jinja2 template

Jinja2 tutorial

yaml load ordered_dict

Smart pointers

2019-09-17T03:55:00.003-07:00

https://lokiastari.com/blog/2015/01/15/c-plus-plus-by-example-smart-pointer-part-ii/

2019-09-17T03:52:00.001-07:00

COPY and SWAP idiom

https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

swap and move

Why do we need the copy-and-swap idiom?

Any class that manages a resource (a wrapper, like a smart pointer) needs to implement The Big Three. While the goals and implementation of the copy-constructor and destructor are straightforward, the copy-assignment operator is arguably the most nuanced and difficult. How should it be done? What pitfalls need to be avoided?

The copy-and-swap idiom is the solution, and elegantly assists the assignment operator in achieving two things: avoiding code duplication, and providing a strong exception guarantee.

How does it work?

Conceptually, it works by using the copy-constructor's functionality to create a local copy of the data, then takes the copied data with a swap function, swapping the old data with the new data. The temporary copy then destructs, taking the old data with it. We are left with a copy of the new data.

In order to use the copy-and-swap idiom, we need three things: a working copy-constructor, a working destructor (both are the basis of any wrapper, so should be complete anyway), and a swapfunction.

A swap function is a non-throwing function that swaps two objects of a class, member for member. We might be tempted to use std::swap instead of providing our own, but this would be impossible; std::swap uses the copy-constructor and copy-assignment operator within its implementation, and we'd ultimately be trying to define the assignment operator in terms of itself!

(Not only that, but unqualified calls to swap will use our custom swap operator, skipping over the unnecessary construction and destruction of our class that std::swap would entail.)

An in-depth explanation

The goal

Let's consider a concrete case. We want to manage, in an otherwise useless class, a dynamic array. We start with a working constructor, copy-constructor, and destructor:

This class almost manages the array successfully, but it needs operator= to work correctly.

A failed solution

Here's how a naive implementation might look:

And we say we're finished; this now manages an array, without leaks. However, it suffers from three problems, marked sequentially in the code as (n).

The first is the self-assignment test. This check serves two purposes: it's an easy way to prevent us from running needless code on self-assignment, and it protects us from subtle bugs (such as deleting the array only to try and copy it). But in all other cases it merely serves to slow the program down, and act as noise in the code; self-assignment rarely occurs, so most of the time this check is a waste. It would be better if the operator could work properly without it.
The second is that it only provides a basic exception guarantee. If new int[mSize] fails, *this will have been modified. (Namely, the size is wrong and the data is gone!) For a strong exception guarantee, it would need to be something akin to:
The code has expanded! Which leads us to the third problem: code duplication. Our assignment operator effectively duplicates all the code we've already written elsewhere, and that's a terrible thing.

In our case, the core of it is only two lines (the allocation and the copy), but with more complex resources this code bloat can be quite a hassle. We should strive to never repeat ourselves.

(One might wonder: if this much code is needed to manage one resource correctly, what if my class manages more than one? While this may seem to be a valid concern, and indeed it requires non-trivial try/catch clauses, this is a non-issue. That's because a class should manage one resource only!)

A successful solution

As mentioned, the copy-and-swap idiom will fix all these issues. But right now, we have all the requirements except one: a swap function. While The Rule of Three successfully entails the existence of our copy-constructor, assignment operator, and destructor, it should really be called "The Big Three and A Half": any time your class manages a resource it also makes sense to provide a swap function.

We need to add swap functionality to our class, and we do that as follows†:

(Here is the explanation why public friend swap.) Now not only can we swap our dumb_array's, but swaps in general can be more efficient; it merely swaps pointers and sizes, rather than allocating and copying entire arrays. Aside from this bonus in functionality and efficiency, we are now ready to implement the copy-and-swap idiom.

Without further ado, our assignment operator is:

And that's it! With one fell swoop, all three problems are elegantly tackled at once.

Why does it work?

We first notice an important choice: the parameter argument is taken by-value. While one could just as easily do the following (and indeed, many naive implementations of the idiom do):

We lose an important optimization opportunity. Not only that, but this choice is critical in C++11, which is discussed later. (On a general note, a remarkably useful guideline is as follows: if you're going to make a copy of something in a function, let the compiler do it in the parameter list.‡)

Either way, this method of obtaining our resource is the key to eliminating code duplication: we get to use the code from the copy-constructor to make the copy, and never need to repeat any bit of it. Now that the copy is made, we are ready to swap.

Observe that upon entering the function that all the new data is already allocated, copied, and ready to be used. This is what gives us a strong exception guarantee for free: we won't even enter the function if construction of the copy fails, and it's therefore not possible to alter the state of *this. (What we did manually before for a strong exception guarantee, the compiler is doing for us now; how kind.)

At this point we are home-free, because swap is non-throwing. We swap our current data with the copied data, safely altering our state, and the old data gets put into the temporary. The old data is then released when the function returns. (Where upon the parameter's scope ends and its destructor is called.)

Because the idiom repeats no code, we cannot introduce bugs within the operator. Note that this means we are rid of the need for a self-assignment check, allowing a single uniform implementation of operator=. (Additionally, we no longer have a performance penalty on non-self-assignments.)

And that is the copy-and-swap idiom.

What about C++11?

The next version of C++, C++11, makes one very important change to how we manage resources: the Rule of Three is now The Rule of Four (and a half). Why? Because not only do we need to be able to copy-construct our resource, we need to move-construct it as well.

Luckily for us, this is easy:

What's going on here? Recall the goal of move-construction: to take the resources from another instance of the class, leaving it in a state guaranteed to be assignable and destructible.

So what we've done is simple: initialize via the default constructor (a C++11 feature), then swap with other; we know a default constructed instance of our class can safely be assigned and destructed, so we know other will be able to do the same, after swapping.

(Note that some compilers do not support constructor delegation; in this case, we have to manually default construct the class. This is an unfortunate but luckily trivial task.)

Why does that work?

That is the only change we need to make to our class, so why does it work? Remember the ever-important decision we made to make the parameter a value and not a reference:

Now, if other is being initialized with an rvalue, it will be move-constructed. Perfect. In the same way C++03 let us re-use our copy-constructor functionality by taking the argument by-value, C++11 will automatically pick the move-constructor when appropriate as well. (And, of course, as mentioned in previously linked article, the copying/moving of the value may simply be elided altogether.)

And so concludes the copy-and-swap idiom.

2019-08-23T09:49:00.001-07:00

Lock free programming:

https://preshing.com/20120612/an-introduction-to-lock-free-programming/

memory ordering:
https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-ordering/

Kernel tuning:

cat /proc/cmdline
BOOT_IMAGE=/vmlinuz-3.10.0-123.el7.x86_64 root=UUID=d34860b6-1642-4a58-9a45-80e398065f28 ro vconsole.keymap=us crashkernel=auto vconsole.font=latarcyrheb-sun16 rhgb quiet console=ttyS1 intel_idle.max_cstate=0 processor.max_cstate=0 idle=poll hugepages=16384 isolcpus=1-8,10-35 nohz_full=1-8,10-35 rcu_nocbs=1-8,10-35 thermal.off=1 gbpages nosoftlockup

software tuning

crack inter

2019-08-13T10:05:00.002-07:00

dvt-nj01-sv104:messages $ wireshark -X lua_script:/home/enguang/work/git/tng/fdk/yaml/messages/vfm_dissector.lua&

https://github.com/Open-Markets-Initiative/wireshark-lua

2019-07-11T05:06:00.004-07:00

Illustrated Guide to Monitoring and Tuning the Linux Networking Stack: Receiving Data:

Tuning receive buf

2019-05-10T07:33:00.003-07:00

memory allocation

First, some clarification. You asked: ... my program a.out terminates already, there is no other process that is maintaining this memory cache - or, is there one?

Everything we are talking about is within the lifetime of a single process: the process always returns all allocated memory when it exits. There is no cache that outlives the process¹. The memory is returned even without any help from the runtime allocator: the OS simply "takes it back" when the process is terminated. So there is no system-wide leak possible from terminated applications with normal allocations.

Now what Valgrind is reporting is memory that is in use at the moment the process terminated, but before the OS cleans everything up. It works at the runtime library level, and not at the OS level. So it's saying "Hey, when the program finished, there were 72,000 bytes that hadn't been returned to the runtime" but an unstated implication is that "these allocations will be cleaned up shortly by the OS".

The Underlying Questions

The code and Valgrind output shown doesn't really correlate well with the titular question, so let's break them apart. First we'll just try to answer the questions you asked about allocators: why they exist and why they don't generally don't immediately return freed memory to the OS, ignoring the example.

You asked:

1) Why keep them in an internal cache? If it is for speed, how is it faster? Yes, the OS needs to maintain a data structure to keep track of memory allocation, but this the maintainer of this cache also needs to do so.

This is sort of two questions in one: one is why bother having a userland runtime allocator at all, and then the other one is (perhaps?) why don't these allocators immediately return memory to the OS when it is freed. They are related, but let's tackle them one at a time.

Why Runtime Allocators Exist

Why not just rely on the OS memory allocation routines?

Many operating systems, including most Linux and other Unix-like operating systems, simply don't have an OS system call to allocate and free arbitrary blocks of memory. Unix-alikes offer brk which only grows or shrinks one contiguous block of memory - you have no way to "free" arbitrary earlier allocations. They also offer mmap which allows you to independently allocate and free chunks of memory, but these allocate on a PAGE_SIZE granularity, which on Linux is 4096 bytes. So if you want request 32 bytes, you'll have to waste 4096 - 32 == 4064 bytes if you don't have your own allocator. On these operating systems you practically need a separate memory allocation runtime which turns these coarse-grained tools into something capable of efficiently allocating small blocks.

Windows is a bit different. It has the HeapAlloc call, which is part of the "OS" and does offer malloc-like capabilities of allocating and freeing arbitrarily sized chunks of memory. With somecompilers then, malloc is just implemented as a thin wrapper around HeapAlloc (the performance of this call has improved greatly in recent Windows versions, making this feasible). Still, while HeapAlloc is part of the OS it isn't implemented in the kernel - it is also mostly implemented in a user-mode library, managing a list of free and used blocks, with occasional kernel calls to get chunks of memory from the kernel. So it is mostly malloc in another disguise and any memory it is holding on to is also not available to any other processes.
Performance! Even if there were appropriate kernel-level calls to allocate arbitrary blocks of memory, the simple overhead roundtrip to the kernel is usually hundreds of nanoseconds or more. A well-tuned malloc allocation or free, on other hand, is often only a dozen instructions and may complete in 10 ns or less. On top of that, system calls can't "trust their input" and so must carefully validate parameters passed from user-space. In the case of free this means that it much check that the user passed a pointer which is valid! Most runtime free implements simply crash or silently corrupt memory since there is no responsibility to protect a process from itself.
Closer link to the rest of the language runtime. The functions you use to allocate memory in C++, namely new, malloc and friends, are part of an defined by the language. It is then entirely natural to implement them as part of the runtime that implements the rest of the language, rather than the OS which is for the most part language-agnostic. For example, the language may have specific alignment requirements for various objects, which can best be handled by language aware allocators. Changes to the language or compiler might also imply necessary changes to the allocation routines, and it would be a tough call to hope for the kernel to be updated to accommodate your language features!

Why Not Return Memory to the OS

Your example doesn't show it, but you asked and if you wrote a different test you would probably find that after allocating and then freeing a bunch of memory, your processes resident set size and/or virtual size as reported by the OS might not decrease after the free. That is, it seems like the process holds on to the memory even though you have freed it. This is in fact true of many mallocimplementations. First, note that this is not a leak per se - the unreturned memory is still available to the process that allocated it, even if not to other processes.

Why do they do that? Here are some reasons:

The kernel API makes it hard. For the old-school brk and sbrk system calls, it simply isn't feasible to return freed memory unless it happens to be at the end of very last block allocated from brk or sbrk. That's because the abstraction offered by these calls is a single large contiguous region that you can only extend from one end. You can't hand back memory from the middle of it. Rather than trying to support the unusual case where all the freed memory happens to be at the end of brk region, most allocators don't even bother.

The mmap call is more flexible (and this discussion generally applies also to Windows where VirtualAlloc is the mmap equivalent), allowing you to at least return memory at a page granularity - but even that is hard! You can't return a page until all allocations that are part of that page are freed. Depending on the size and allocation/free pattern of the application that may be common or uncommon. A case where it works well is for large allocations - greater than a page. Here you're guaranteed to be able to free most of the allocation if it was done via mmap and indeed some modern allocators satisfy large allocations directly from mmap and free them back to the OS with munmap. For glibc (and by extension the C++ allocation operators), you can even control this threshold:
```
M_MMAP_THRESHOLD
  For allocations greater than or equal to the limit specified
  (in bytes) by M_MMAP_THRESHOLD that can't be satisfied from
  the free list, the memory-allocation functions employ mmap(2)
  instead of increasing the program break using sbrk(2).

  Allocating memory using mmap(2) has the significant advantage
  that the allocated memory blocks can always be independently
  released back to the system.  (By contrast, the heap can be
  trimmed only if memory is freed at the top end.)  On the other
  hand, there are some disadvantages to the use of mmap(2):
  deallocated space is not placed on the free list for reuse by
  later allocations; memory may be wasted because mmap(2)
  allocations must be page-aligned; and the kernel must perform
  the expensive task of zeroing out memory allocated via
  mmap(2).  Balancing these factors leads to a default setting
  of 128*1024 for the M_MMAP_THRESHOLD parameter.
```
So by default allocations of 128K or more will be allocated by the runtime directly from the OS and freed back to the OS on free. So sometimes you will see the behavior you might have expected is always the case.
Performance! Every kernel call is expensive, as described in the other list above. Memory that is freed by a process will be needed shortly later to satisfy another allocation. Rather than trying to return it to the OS, a relatively heavyweight operation, why not just keep it around on a free listto satisfy future allocations? As pointed out in the man page entry, this also avoids the overhead of zeroing out all the memory returned by the kernel. It also gives the best chance of good cache behavior since the process is continually re-using the same region of the address space. Finally, it avoids TLB flushes which would be imposed by munmap (and possibly by shrinking via brk).
The "problem" of not returning memory is the worst for long-lived processes that allocate a bunch of memory at some point, free it and then never allocate that much again. I.e., processes whose allocation high-water mark is larger than their long term typical allocation amount. Most processes just don't follow that pattern, however. Processes often free a lot of memory, but allocate at a rate such that their overall memory use is constant or perhaps increasing. Applications that do have the "big then small" live size pattern could perhaps force the issue with malloc_trim.
Virtual memory helps mitigate the issue. So far I've been throwing around terms like "allocated memory" without really defining what it means. If a program allocates and then frees 2 GB of memory and then sits around doing nothing, is it wasting 2 GB of actual DRAM plugged into your motherboard somewhere? Probably not. It is using 2 GB of virtual address space in your process, sure, but virtual address space is per-process, so that doesn't directly take anything away from other processes. If the process actually wrote to the memory at some point, it would be allocated physical memory (yes, DRAM) - after freeing it, you are - by definition - no longer using it. At this point the OS may reclaim those physical pages by use for someone else.

Now this still requires you have swap to absorb the dirty not-used pages, but some allocators are smart: they can issue a madvise(..., MADV_DONTNEED) call which tells the OS "this range doesn't have anything useful, you don't have to preserve its contents in swap". It still leaves the virtual address space mapped in the process and usable later (zero filled) and so it's more efficient than munmap and a subsequent mmap, but it avoid pointlessly swapping freed memory regions to swap.²

The Demonstrated Code

As pointed out in this answer your test with vector<int> isn't really testing anything because an empty, unused std::vector<int> v won't even create the vector object as long as you are using some minimal level of optimization. Even without optimization, no allocation is likely to occur because most vector implementations allocate on first insertion, and not in the constructor. Finally, even if you are using some unusual compiler or library that does an allocation, it will be for a handful of bytes, not the ~72,000 bytes Valgrind is reporting.

You should do something like this to actually see the impact of a vector allocation:

#include <vector>

volatile vector<int> *sink;

int main() {
    std::vector<int> v(12345678);
    sink = &v;
}

That results in actual allocation and de-allocation. It isn't going to change the Valgrind output, however, since the vector allocation is correctly freed before the program exits, so there is no issue as far as Valgrind is concerned.

At a high level, Valgrind basically categorizes things into "definite leaks" and "not freed at exit". The former occur when the program no longer has a reference to a pointer to memory that it allocated. It cannot free such memory and so has leaked it. Memory which hasn't been freed at exit may be a "leak" - i.e., objects that should have been freed, but it may also simply be memory that the developer knew would live the length of the program and so doesn't need to be explicitly freed (because of order-of-destruction issues for globals, especially when shared libraries are involved, it may be very hard to reliably free memory associated with global or static objects even if you wanted to).

¹ In some cases some deliberately special allocations may outlive the process, such as shared memory and memory mapped files, but that doesn't relate to plain C++ allocations and you can ignore it for the purposes of this discussion.

² Recent Linux kernels also have the Linux-specific MADV_FREE which seems to have similar semantics to MADV_DONTNEED.

2019-05-04T12:15:00.002-07:00

2019-01-18T06:51:00.001-08:00

https://clang.llvm.org/extra/modularize.html

swap idiom

Overview

Why do we need the copy-and-swap idiom?

The copy-and-swap idiom is the solution, and elegantly assists the assignment operator in achieving two things: avoiding code duplication, and providing a strong exception guarantee.

How does it work?

(Not only that, but unqualified calls to swap will use our custom swap operator, skipping over the unnecessary construction and destruction of our class that std::swap would entail.)

An in-depth explanation

The goal

Let's consider a concrete case. We want to manage, in an otherwise useless class, a dynamic array. We start with a working constructor, copy-constructor, and destructor:

#include <algorithm> // std::copy
#include <cstddef> // std::size_t

class dumb_array
{
public:
    // (default) constructor
    dumb_array(std::size_t size = 0)
        : mSize(size),
          mArray(mSize ? new int[mSize]() : nullptr)
    {
    }

    // copy-constructor
    dumb_array(const dumb_array& other)
        : mSize(other.mSize),
          mArray(mSize ? new int[mSize] : nullptr),
    {
        // note that this is non-throwing, because of the data
        // types being used; more attention to detail with regards
        // to exceptions must be given in a more general case, however
        std::copy(other.mArray, other.mArray + mSize, mArray);
    }

    // destructor
    ~dumb_array()
    {
        delete [] mArray;
    }

private:
    std::size_t mSize;
    int* mArray;
};

This class almost manages the array successfully, but it needs operator= to work correctly.

A failed solution

Here's how a naive implementation might look:

// the hard part
dumb_array& operator=(const dumb_array& other)
{
    if (this != &other) // (1)
    {
        // get rid of the old data...
        delete [] mArray; // (2)
        mArray = nullptr; // (2) *(see footnote for rationale)

        // ...and put in the new
        mSize = other.mSize; // (3)
        mArray = mSize ? new int[mSize] : nullptr; // (3)
        std::copy(other.mArray, other.mArray + mSize, mArray); // (3)
    }

    return *this;
}

And we say we're finished; this now manages an array, without leaks. However, it suffers from three problems, marked sequentially in the code as (n).

The first is the self-assignment test. This check serves two purposes: it's an easy way to prevent us from running needless code on self-assignment, and it protects us from subtle bugs (such as deleting the array only to try and copy it). But in all other cases it merely serves to slow the program down, and act as noise in the code; self-assignment rarely occurs, so most of the time this check is a waste. It would be better if the operator could work properly without it.

The second is that it only provides a basic exception guarantee. If new int[mSize] fails, *this will have been modified. (Namely, the size is wrong and the data is gone!) For a strong exception guarantee, it would need to be something akin to:

dumb_array& operator=(const dumb_array& other)
{
    if (this != &other) // (1)
    {
        // get the new data ready before we replace the old
        std::size_t newSize = other.mSize;
        int* newArray = newSize ? new int[newSize]() : nullptr; // (3)
        std::copy(other.mArray, other.mArray + newSize, newArray); // (3)

        // replace the old data (all are non-throwing)
        delete [] mArray;
        mSize = newSize;
        mArray = newArray;
    }

    return *this;
}

The code has expanded! Which leads us to the third problem: code duplication. Our assignment operator effectively duplicates all the code we've already written elsewhere, and that's a terrible thing.

In our case, the core of it is only two lines (the allocation and the copy), but with more complex resources this code bloat can be quite a hassle. We should strive to never repeat ourselves.

A successful solution

We need to add swap functionality to our class, and we do that as follows†:

class dumb_array
{
public:
    // ...

    friend void swap(dumb_array& first, dumb_array& second) // nothrow
    {
        // enable ADL (not necessary in our case, but good practice)
        using std::swap;

        // by swapping the members of two objects,
        // the two objects are effectively swapped
        swap(first.mSize, second.mSize);
        swap(first.mArray, second.mArray);
    }

    // ...
};

Without further ado, our assignment operator is:

dumb_array& operator=(dumb_array other) // (1)
{
    swap(*this, other); // (2)

    return *this;
}

And that's it! With one fell swoop, all three problems are elegantly tackled at once.

Why does it work?

We first notice an important choice: the parameter argument is taken by-value. While one could just as easily do the following (and indeed, many naive implementations of the idiom do):

dumb_array& operator=(const dumb_array& other)
{
    dumb_array temp(other);
    swap(*this, temp);

    return *this;
}

And that is the copy-and-swap idiom.

What about C++11?

Luckily for us, this is easy:

class dumb_array
{
public:
    // ...

    // move constructor
    dumb_array(dumb_array&& other)
        : dumb_array() // initialize via default constructor, C++11 only
    {
        swap(*this, other);
    }

    // ...
};

What's going on here? Recall the goal of move-construction: to take the resources from another instance of the class, leaving it in a state guaranteed to be assignable and destructible.

(Note that some compilers do not support constructor delegation; in this case, we have to manually default construct the class. This is an unfortunate but luckily trivial task.)

Why does that work?

That is the only change we need to make to our class, so why does it work? Remember the ever-important decision we made to make the parameter a value and not a reference:

dumb_array& operator=(dumb_array other); // (1)

And so concludes the copy-and-swap idiom.

Footnotes

*Why do we set mArray to null? Because if any further code in the operator throws, the destructor of dumb_array might be called; and if that happens without setting it to null, we attempt to delete memory that's already been deleted! We avoid this by setting it to null, as deleting null is a no-operation.

†There are other claims that we should specialize std::swap for our type, provide an in-class swap along-side a free-function swap, etc. But this is all unnecessary: any proper use of swapwill be through an unqualified call, and our function will be found through ADL. One function will do.

‡The reason is simple: once you have the resource to yourself, you may swap and/or move it (C++11) anywhere it needs to be. And by making the copy in the parameter list, you maximize optimization.

std::void_t

2018-12-16T14:43:00.002-08:00

void_t

I watched Walter Brown's talk at Cppcon14 about modern template programming (Part I, Part II) where he presented his void_t SFINAE technique.

Example:
Given a simple variable template that evaluates to void if all template arguments are well formed:

and the following trait that checks for the existence of a member variable called member:

I tried to understand why and how this works. Therefore a tiny example:

1. has_member< A >

has_member< A , void_t< decltype( A::member ) > >
- A::member exists
- decltype( A::member ) is well-formed
- void_t<> is valid and evaluates to void
has_member< A , void > and therefore it chooses the specialized template
has_member< T , void > and evaluates to true_type

2. has_member

has_member >
- B::member does not exist
- decltype( B::member ) is ill-formed and fails silently (sfinae)
- has_member so this template is discarded
compiler finds has_member with void as default argument
has_member evaluates to false_type

http://ideone.com/HCTlBb

Questions:
1. Is my understanding of this correct?
2. Walter Brown states that the default argument has to be the exact same type as the one used in void_t for it to work. Why is that? (I don't see why this types need to match, doesn't just any default type does the job?)

When you write has_member<A>::value, the compiler looks up the name has_member and finds the primary class template, that is, this declaration:

(In the OP, that's written as a definition.)

The template argument list <A> is compared to the template parameter list of this primary template. Since the primary template has two parameters, but you only supplied one, the remaining parameter is defaulted to the default template argument: void. It's as if you had written has_member<A, void>::value.

Now, the template parameter list is compared against any specializations of the template has_member. Only if no specialization matches, the definition of the primary template is used as a fall-back. So the partial specialization is taken into account:

The compiler tries to match the template arguments A, void with the patterns defined in the partial specialization: T and void_t<..> one by one. First, template argument deduction is performed. The partial specialization above is still a template with template-parameters that need to be "filled" by arguments.

The first pattern, T, allows the compiler to deduce the template-parameter T. This is a trivial deduction, but consider a pattern like T const&, where we could still deduce T. For the pattern Tand the template argument A, we deduce T to be A.

In the second pattern void_t< decltype( T::member ) >, the template-parameter T appears in a context where it cannot be deduced from any template argument. There are two reasons for this:

The expression inside decltype is explicitly excluded from template argument deduction. I guess this is because it can be arbitrarily complex.
Even if we used a pattern without decltype like void_t< T >, then the deduction of Thappens on the resolved alias template. That is, we resolve the alias template and then try to deduce the type T from the resulting pattern. The resulting pattern however is void, which is not dependent on T and therefore does not allow us to find a specific type for T. This is similar to the mathematical problem of trying to invert a constant function (in the mathematical sense of those terms).

Template argument deduction is finished^(*), now the deduced template arguments are substituted. This creates a specialization that looks like this:
The type void_t< decltype( A::member ) > > can now be evaluated. It is well-formed after substitution, hence, no Substitution Failure occurs. We get:
Now, we can compare the template parameter list of this specialization with the template arguments supplied to the original has_member<A>::value. Both types match exactly, so this partial specialization is chosen.

On the other hand, when we define the template as:
We end up with the same specialization:
but our template argument list for has_member<A>::value now is <A, int>. The arguments do not match the parameters of the specialization, and the primary template is chosen as a fall-back.

^(*) The Standard, IMHO confusingly, includes the substitution process and the matching of explicitly specified template arguments in the template argument deduction process. For example (post-N4296) [temp.class.spec.match]/2:

A partial specialization matches a given actual template argument list if the template arguments of the partial specialization can be deduced from the actual template argument list.

But this does not just mean that all template-parameters of the partial specialization have to be deduced; it also means that substitution must succeed and (as it seems?) the template arguments have to match the (substituted) template parameters of the partial specialization. Note that I'm not completely aware of where the Standard specifies the comparison between the substituted argument list and the supplied argument list.

2018-12-08T11:36:00.001-08:00

GNU format attributes

__attribute__ format(printf, 2, 3)

a variadic logger

2018-11-25T09:06:00.001-08:00

11/25/2018:

1. C++ sanitizers:

ubsan: undefined behavior sanitizer
asan: address sanitizer
tsan: thread sanitizer
msan: memory sanitizer

2. C++ open source codes:

{fmt}
spdlog

3. C++ website:
3.1) Compiler Explorer
3.2) Cpp insights

4. CppCon 2015: Chandler Carruth "Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!"

Understanding dynamic loading

2018-11-08T20:54:00.000-08:00

Shared Libraries: Understanding Dynamic Loading

CMake tutorial

Modern CMake

An introduction of modern CMake