datapath/meter.c

   1 /*
   2  * Copyright (c) 2017 Nicira, Inc.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of version 2 of the GNU General Public
   6  * License as published by the Free Software Foundation.
   7  */
   8
   9 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  10
  11 #include <linux/if.h>
  12 #include <linux/skbuff.h>
  13 #include <linux/ip.h>
  14 #include <linux/kernel.h>
  15 #include <linux/openvswitch.h>
  16 #include <linux/netlink.h>
  17 #include <linux/rculist.h>
  18
  19 #include <net/netlink.h>
  20 #include <net/genetlink.h>
  21
  22 #include "datapath.h"
  23 #include "meter.h"
  24
  25 #define METER_HASH_BUCKETS 1024
  26
  27 static const struct nla_policy meter_policy[OVS_METER_ATTR_MAX + 1] = {
  28         [OVS_METER_ATTR_ID] = { .type = NLA_U32, },
  29         [OVS_METER_ATTR_KBPS] = { .type = NLA_FLAG },
  30         [OVS_METER_ATTR_STATS] = { .len = sizeof(struct ovs_flow_stats) },
  31         [OVS_METER_ATTR_BANDS] = { .type = NLA_NESTED },
  32         [OVS_METER_ATTR_USED] = { .type = NLA_U64 },
  33         [OVS_METER_ATTR_CLEAR] = { .type = NLA_FLAG },
  34         [OVS_METER_ATTR_MAX_METERS] = { .type = NLA_U32 },
  35         [OVS_METER_ATTR_MAX_BANDS] = { .type = NLA_U32 },
  36 };
  37
  38 static const struct nla_policy band_policy[OVS_BAND_ATTR_MAX + 1] = {
  39         [OVS_BAND_ATTR_TYPE] = { .type = NLA_U32, },
  40         [OVS_BAND_ATTR_RATE] = { .type = NLA_U32, },
  41         [OVS_BAND_ATTR_BURST] = { .type = NLA_U32, },
  42         [OVS_BAND_ATTR_STATS] = { .len = sizeof(struct ovs_flow_stats) },
  43 };
  44
  45 static void ovs_meter_free(struct dp_meter *meter)
  46 {
  47         if (!meter)
  48                 return;
  49
  50         kfree_rcu(meter, rcu);
  51 }
  52
  53 static struct hlist_head *meter_hash_bucket(const struct datapath *dp,
  54                                             u32 meter_id)
  55 {
  56         return &dp->meters[meter_id & (METER_HASH_BUCKETS - 1)];
  57 }
  58
  59 /* Call with ovs_mutex or RCU read lock. */
  60 static struct dp_meter *lookup_meter(const struct datapath *dp,
  61                                      u32 meter_id)
  62 {
  63         struct dp_meter *meter;
  64         struct hlist_head *head;
  65
  66         head = meter_hash_bucket(dp, meter_id);
  67         hlist_for_each_entry_rcu(meter, head, dp_hash_node) {
  68                 if (meter->id == meter_id)
  69                         return meter;
  70         }
  71         return NULL;
  72 }
  73
  74 static void attach_meter(struct datapath *dp, struct dp_meter *meter)
  75 {
  76         struct hlist_head *head = meter_hash_bucket(dp, meter->id);
  77
  78         hlist_add_head_rcu(&meter->dp_hash_node, head);
  79 }
  80
  81 static void detach_meter(struct dp_meter *meter)
  82 {
  83         ASSERT_OVSL();
  84         if (meter)
  85                 hlist_del_rcu(&meter->dp_hash_node);
  86 }
  87
  88 static struct sk_buff *
  89 ovs_meter_cmd_reply_start(struct genl_info *info, u8 cmd,
  90                           struct ovs_header **ovs_reply_header)
  91 {
  92         struct sk_buff *skb;
  93         struct ovs_header *ovs_header = info->userhdr;
  94
  95         skb = nlmsg_new(NLMSG_DEFAULT_SIZE, GFP_ATOMIC);
  96         if (!skb)
  97                 return ERR_PTR(-ENOMEM);
  98
  99         *ovs_reply_header = genlmsg_put(skb, info->snd_portid,
 100                                         info->snd_seq,
 101                                         &dp_meter_genl_family, 0, cmd);
 102         if (!*ovs_reply_header) {
 103                 nlmsg_free(skb);
 104                 return ERR_PTR(-EMSGSIZE);
 105         }
 106         (*ovs_reply_header)->dp_ifindex = ovs_header->dp_ifindex;
 107
 108         return skb;
 109 }
 110
 111 static int ovs_meter_cmd_reply_stats(struct sk_buff *reply, u32 meter_id,
 112                                      struct dp_meter *meter)
 113 {
 114         struct nlattr *nla;
 115         struct dp_meter_band *band;
 116         u16 i;
 117
 118         if (nla_put_u32(reply, OVS_METER_ATTR_ID, meter_id))
 119                 goto error;
 120
 121         if (!meter)
 122                 return 0;
 123
 124         if (nla_put(reply, OVS_METER_ATTR_STATS,
 125                     sizeof(struct ovs_flow_stats), &meter->stats) ||
 126             nla_put_u64_64bit(reply, OVS_METER_ATTR_USED, meter->used,
 127                               OVS_METER_ATTR_PAD))
 128                 goto error;
 129
 130         nla = nla_nest_start(reply, OVS_METER_ATTR_BANDS);
 131         if (!nla)
 132                 goto error;
 133
 134         band = meter->bands;
 135
 136         for (i = 0; i < meter->n_bands; ++i, ++band) {
 137                 struct nlattr *band_nla;
 138
 139                 band_nla = nla_nest_start(reply, OVS_BAND_ATTR_UNSPEC);
 140                 if (!band_nla || nla_put(reply, OVS_BAND_ATTR_STATS,
 141                                          sizeof(struct ovs_flow_stats),
 142                                          &band->stats))
 143                         goto error;
 144                 nla_nest_end(reply, band_nla);
 145         }
 146         nla_nest_end(reply, nla);
 147
 148         return 0;
 149 error:
 150         return -EMSGSIZE;
 151 }
 152
 153 static int ovs_meter_cmd_features(struct sk_buff *skb, struct genl_info *info)
 154 {
 155         struct sk_buff *reply;
 156         struct ovs_header *ovs_reply_header;
 157         struct nlattr *nla, *band_nla;
 158         int err;
 159
 160         reply = ovs_meter_cmd_reply_start(info, OVS_METER_CMD_FEATURES,
 161                                           &ovs_reply_header);
 162         if (IS_ERR(reply))
 163                 return PTR_ERR(reply);
 164
 165         if (nla_put_u32(reply, OVS_METER_ATTR_MAX_METERS, U32_MAX) ||
 166             nla_put_u32(reply, OVS_METER_ATTR_MAX_BANDS, DP_MAX_BANDS))
 167                 goto nla_put_failure;
 168
 169         nla = nla_nest_start(reply, OVS_METER_ATTR_BANDS);
 170         if (!nla)
 171                 goto nla_put_failure;
 172
 173         band_nla = nla_nest_start(reply, OVS_BAND_ATTR_UNSPEC);
 174         if (!band_nla)
 175                 goto nla_put_failure;
 176         /* Currently only DROP band type is supported. */
 177         if (nla_put_u32(reply, OVS_BAND_ATTR_TYPE, OVS_METER_BAND_TYPE_DROP))
 178                 goto nla_put_failure;
 179         nla_nest_end(reply, band_nla);
 180         nla_nest_end(reply, nla);
 181
 182         genlmsg_end(reply, ovs_reply_header);
 183         return genlmsg_reply(reply, info);
 184
 185 nla_put_failure:
 186         nlmsg_free(reply);
 187         err = -EMSGSIZE;
 188         return err;
 189 }
 190
 191 #ifndef HAVE_KTIME_GET_NS
 192 #ifndef ktime_to_ns
 193 #define ktime_to_ns(kt)                 ((kt).tv64)
 194 #endif
 195 static inline u64 ktime_get_ns(void)
 196 {
 197         return ktime_to_ns(ktime_get());
 198 }
 199 #endif
 200
 201 static struct dp_meter *dp_meter_create(struct nlattr **a)
 202 {
 203         struct nlattr *nla;
 204         int rem;
 205         u16 n_bands = 0;
 206         struct dp_meter *meter;
 207         struct dp_meter_band *band;
 208         int err;
 209
 210         /* Validate attributes, count the bands. */
 211         if (!a[OVS_METER_ATTR_BANDS])
 212                 return ERR_PTR(-EINVAL);
 213
 214         nla_for_each_nested(nla, a[OVS_METER_ATTR_BANDS], rem)
 215                 if (++n_bands > DP_MAX_BANDS)
 216                         return ERR_PTR(-EINVAL);
 217
 218         /* Allocate and set up the meter before locking anything. */
 219         meter = kzalloc(n_bands * sizeof(struct dp_meter_band) +
 220                         sizeof(*meter), GFP_KERNEL);
 221         if (!meter)
 222                 return ERR_PTR(-ENOMEM);
 223
 224         meter->id = nla_get_u32(a[OVS_METER_ATTR_ID]);
 225         meter->used = div_u64(ktime_get_ns(), 1000 * 1000);
 226         meter->kbps = a[OVS_METER_ATTR_KBPS] ? 1 : 0;
 227         meter->keep_stats = !a[OVS_METER_ATTR_CLEAR];
 228         spin_lock_init(&meter->lock);
 229         if (meter->keep_stats && a[OVS_METER_ATTR_STATS]) {
 230                 meter->stats = *(struct ovs_flow_stats *)
 231                         nla_data(a[OVS_METER_ATTR_STATS]);
 232         }
 233         meter->n_bands = n_bands;
 234
 235         /* Set up meter bands. */
 236         band = meter->bands;
 237         nla_for_each_nested(nla, a[OVS_METER_ATTR_BANDS], rem) {
 238                 struct nlattr *attr[OVS_BAND_ATTR_MAX + 1];
 239                 u32 band_max_delta_t;
 240
 241                 err = nla_parse((struct nlattr **)&attr, OVS_BAND_ATTR_MAX,
 242                                 nla_data(nla), nla_len(nla), band_policy,
 243                                 NULL);
 244                 if (err)
 245                         goto exit_free_meter;
 246
 247                 if (!attr[OVS_BAND_ATTR_TYPE] ||
 248                     !attr[OVS_BAND_ATTR_RATE] ||
 249                     !attr[OVS_BAND_ATTR_BURST]) {
 250                         err = -EINVAL;
 251                         goto exit_free_meter;
 252                 }
 253
 254                 band->type = nla_get_u32(attr[OVS_BAND_ATTR_TYPE]);
 255                 band->rate = nla_get_u32(attr[OVS_BAND_ATTR_RATE]);
 256                 if (band->rate == 0) {
 257                         err = -EINVAL;
 258                         goto exit_free_meter;
 259                 }
 260
 261                 band->burst_size = nla_get_u32(attr[OVS_BAND_ATTR_BURST]);
 262                 /* Figure out max delta_t that is enough to fill any bucket.
 263                  * Keep max_delta_t size to the bucket units:
 264                  * pkts => 1/1000 packets, kilobits => bits.
 265                  *
 266                  * Start with a full bucket.
 267                  */
 268                 band->bucket = (band->burst_size + band->rate) * 1000;
 269                 band_max_delta_t = band->bucket / band->rate;
 270                 if (band_max_delta_t > meter->max_delta_t)
 271                         meter->max_delta_t = band_max_delta_t;
 272                 band++;
 273         }
 274
 275         return meter;
 276
 277 exit_free_meter:
 278         kfree(meter);
 279         return ERR_PTR(err);
 280 }
 281
 282 static int ovs_meter_cmd_set(struct sk_buff *skb, struct genl_info *info)
 283 {
 284         struct nlattr **a = info->attrs;
 285         struct dp_meter *meter, *old_meter;
 286         struct sk_buff *reply;
 287         struct ovs_header *ovs_reply_header;
 288         struct ovs_header *ovs_header = info->userhdr;
 289         struct datapath *dp;
 290         int err;
 291         u32 meter_id;
 292         bool failed;
 293
 294         if (!a[OVS_METER_ATTR_ID]) {
 295                 return -ENODEV;
 296         }
 297
 298         meter = dp_meter_create(a);
 299         if (IS_ERR_OR_NULL(meter))
 300                 return PTR_ERR(meter);
 301
 302         reply = ovs_meter_cmd_reply_start(info, OVS_METER_CMD_SET,
 303                                           &ovs_reply_header);
 304         if (IS_ERR(reply)) {
 305                 err = PTR_ERR(reply);
 306                 goto exit_free_meter;
 307         }
 308
 309         ovs_lock();
 310         dp = get_dp(sock_net(skb->sk), ovs_header->dp_ifindex);
 311         if (!dp) {
 312                 err = -ENODEV;
 313                 goto exit_unlock;
 314         }
 315
 316         meter_id = nla_get_u32(a[OVS_METER_ATTR_ID]);
 317
 318         /* Cannot fail after this. */
 319         old_meter = lookup_meter(dp, meter_id);
 320         detach_meter(old_meter);
 321         attach_meter(dp, meter);
 322         ovs_unlock();
 323
 324         /* Build response with the meter_id and stats from
 325          * the old meter, if any.
 326          */
 327         failed = nla_put_u32(reply, OVS_METER_ATTR_ID, meter_id);
 328         WARN_ON(failed);
 329         if (old_meter) {
 330                 spin_lock_bh(&old_meter->lock);
 331                 if (old_meter->keep_stats) {
 332                         err = ovs_meter_cmd_reply_stats(reply, meter_id,
 333                                                         old_meter);
 334                         WARN_ON(err);
 335                 }
 336                 spin_unlock_bh(&old_meter->lock);
 337                 ovs_meter_free(old_meter);
 338         }
 339
 340         genlmsg_end(reply, ovs_reply_header);
 341         return genlmsg_reply(reply, info);
 342
 343 exit_unlock:
 344         ovs_unlock();
 345         nlmsg_free(reply);
 346 exit_free_meter:
 347         kfree(meter);
 348         return err;
 349 }
 350
 351 static int ovs_meter_cmd_get(struct sk_buff *skb, struct genl_info *info)
 352 {
 353         struct nlattr **a = info->attrs;
 354         u32 meter_id;
 355         struct ovs_header *ovs_header = info->userhdr;
 356         struct ovs_header *ovs_reply_header;
 357         struct datapath *dp;
 358         int err;
 359         struct sk_buff *reply;
 360         struct dp_meter *meter;
 361
 362         if (!a[OVS_METER_ATTR_ID])
 363                 return -EINVAL;
 364
 365         meter_id = nla_get_u32(a[OVS_METER_ATTR_ID]);
 366
 367         reply = ovs_meter_cmd_reply_start(info, OVS_METER_CMD_GET,
 368                                           &ovs_reply_header);
 369         if (IS_ERR(reply))
 370                 return PTR_ERR(reply);
 371
 372         ovs_lock();
 373
 374         dp = get_dp(sock_net(skb->sk), ovs_header->dp_ifindex);
 375         if (!dp) {
 376                 err = -ENODEV;
 377                 goto exit_unlock;
 378         }
 379
 380         /* Locate meter, copy stats. */
 381         meter = lookup_meter(dp, meter_id);
 382         if (!meter) {
 383                 err = -ENOENT;
 384                 goto exit_unlock;
 385         }
 386
 387         spin_lock_bh(&meter->lock);
 388         err = ovs_meter_cmd_reply_stats(reply, meter_id, meter);
 389         spin_unlock_bh(&meter->lock);
 390         if (err)
 391                 goto exit_unlock;
 392
 393         ovs_unlock();
 394
 395         genlmsg_end(reply, ovs_reply_header);
 396         return genlmsg_reply(reply, info);
 397
 398 exit_unlock:
 399         ovs_unlock();
 400         nlmsg_free(reply);
 401         return err;
 402 }
 403
 404 static int ovs_meter_cmd_del(struct sk_buff *skb, struct genl_info *info)
 405 {
 406         struct nlattr **a = info->attrs;
 407         u32 meter_id;
 408         struct ovs_header *ovs_header = info->userhdr;
 409         struct ovs_header *ovs_reply_header;
 410         struct datapath *dp;
 411         int err;
 412         struct sk_buff *reply;
 413         struct dp_meter *old_meter;
 414
 415         if (!a[OVS_METER_ATTR_ID])
 416                 return -EINVAL;
 417         meter_id = nla_get_u32(a[OVS_METER_ATTR_ID]);
 418
 419         reply = ovs_meter_cmd_reply_start(info, OVS_METER_CMD_DEL,
 420                                           &ovs_reply_header);
 421         if (IS_ERR(reply))
 422                 return PTR_ERR(reply);
 423
 424         ovs_lock();
 425
 426         dp = get_dp(sock_net(skb->sk), ovs_header->dp_ifindex);
 427         if (!dp) {
 428                 err = -ENODEV;
 429                 goto exit_unlock;
 430         }
 431
 432         old_meter = lookup_meter(dp, meter_id);
 433         if (old_meter) {
 434                 spin_lock_bh(&old_meter->lock);
 435                 err = ovs_meter_cmd_reply_stats(reply, meter_id, old_meter);
 436                 WARN_ON(err);
 437                 spin_unlock_bh(&old_meter->lock);
 438                 detach_meter(old_meter);
 439         }
 440         ovs_unlock();
 441         ovs_meter_free(old_meter);
 442         genlmsg_end(reply, ovs_reply_header);
 443         return genlmsg_reply(reply, info);
 444
 445 exit_unlock:
 446         ovs_unlock();
 447         nlmsg_free(reply);
 448         return err;
 449 }
 450
 451 /* Meter action execution.
 452  *
 453  * Return true 'meter_id' drop band is triggered. The 'skb' should be
 454  * dropped by the caller'.
 455  */
 456 bool ovs_meter_execute(struct datapath *dp, struct sk_buff *skb,
 457                        struct sw_flow_key *key, u32 meter_id)
 458 {
 459         struct dp_meter *meter;
 460         struct dp_meter_band *band;
 461         long long int now_ms = div_u64(ktime_get_ns(), 1000 * 1000);
 462         long long int long_delta_ms;
 463         u32 delta_ms;
 464         u32 cost;
 465         int i, band_exceeded_max = -1;
 466         u32 band_exceeded_rate = 0;
 467
 468         meter = lookup_meter(dp, meter_id);
 469         /* Do not drop the packet when there is no meter. */
 470         if (!meter)
 471                 return false;
 472
 473         /* Lock the meter while using it. */
 474         spin_lock(&meter->lock);
 475
 476         long_delta_ms = (now_ms - meter->used); /* ms */
 477
 478         /* Make sure delta_ms will not be too large, so that bucket will not
 479          * wrap around below.
 480          */
 481         delta_ms = (long_delta_ms > (long long int)meter->max_delta_t)
 482                    ? meter->max_delta_t : (u32)long_delta_ms;
 483
 484         /* Update meter statistics.
 485          */
 486         meter->used = now_ms;
 487         meter->stats.n_packets += 1;
 488         meter->stats.n_bytes += skb->len;
 489
 490         /* Bucket rate is either in kilobits per second, or in packets per
 491          * second.  We maintain the bucket in the units of either bits or
 492          * 1/1000th of a packet, correspondingly.
 493          * Then, when rate is multiplied with milliseconds, we get the
 494          * bucket units:
 495          * msec * kbps = bits, and
 496          * msec * packets/sec = 1/1000 packets.
 497          *
 498          * 'cost' is the number of bucket units in this packet.
 499          */
 500         cost = (meter->kbps) ? skb->len * 8 : 1000;
 501
 502         /* Update all bands and find the one hit with the highest rate. */
 503         for (i = 0; i < meter->n_bands; ++i) {
 504                 long long int max_bucket_size;
 505
 506                 band = &meter->bands[i];
 507                 max_bucket_size = (band->burst_size + band->rate) * 1000LL;
 508
 509                 band->bucket += delta_ms * band->rate;
 510                 if (band->bucket > max_bucket_size)
 511                         band->bucket = max_bucket_size;
 512
 513                 if (band->bucket >= cost) {
 514                         band->bucket -= cost;
 515                 } else if (band->rate > band_exceeded_rate) {
 516                         band_exceeded_rate = band->rate;
 517                         band_exceeded_max = i;
 518                 }
 519         }
 520
 521         if (band_exceeded_max >= 0) {
 522                 /* Update band statistics. */
 523                 band = &meter->bands[band_exceeded_max];
 524                 band->stats.n_packets += 1;
 525                 band->stats.n_bytes += skb->len;
 526
 527                 /* Drop band triggered, let the caller drop the 'skb'.  */
 528                 if (band->type == OVS_METER_BAND_TYPE_DROP) {
 529                         spin_unlock(&meter->lock);
 530                         return true;
 531                 }
 532         }
 533
 534         spin_unlock(&meter->lock);
 535         return false;
 536 }
 537
 538 static struct genl_ops dp_meter_genl_ops[] = {
 539         { .cmd = OVS_METER_CMD_FEATURES,
 540                 .flags = 0,               /* OK for unprivileged users. */
 541                 .policy = meter_policy,
 542                 .doit = ovs_meter_cmd_features
 543         },
 544         { .cmd = OVS_METER_CMD_SET,
 545                 .flags = GENL_ADMIN_PERM, /* Requires CAP_NET_ADMIN
 546                                            *  privilege.
 547                                            */
 548                 .policy = meter_policy,
 549                 .doit = ovs_meter_cmd_set,
 550         },
 551         { .cmd = OVS_METER_CMD_GET,
 552                 .flags = 0,               /* OK for unprivileged users. */
 553                 .policy = meter_policy,
 554                 .doit = ovs_meter_cmd_get,
 555         },
 556         { .cmd = OVS_METER_CMD_DEL,
 557                 .flags = GENL_ADMIN_PERM, /* Requires CAP_NET_ADMIN
 558                                            *  privilege.
 559                                            */
 560                 .policy = meter_policy,
 561                 .doit = ovs_meter_cmd_del
 562         },
 563 };
 564
 565 static const struct genl_multicast_group ovs_meter_multicast_group = {
 566         .name = OVS_METER_MCGROUP,
 567 };
 568
 569 struct genl_family dp_meter_genl_family __ro_after_init = {
 570         .hdrsize = sizeof(struct ovs_header),
 571         .name = OVS_METER_FAMILY,
 572         .version = OVS_METER_VERSION,
 573         .maxattr = OVS_METER_ATTR_MAX,
 574         .netnsok = true,
 575         .parallel_ops = true,
 576         .ops = dp_meter_genl_ops,
 577         .n_ops = ARRAY_SIZE(dp_meter_genl_ops),
 578         .mcgrps = &ovs_meter_multicast_group,
 579         .n_mcgrps = 1,
 580         .module = THIS_MODULE,
 581 };
 582
 583 int ovs_meters_init(struct datapath *dp)
 584 {
 585         int i;
 586
 587         dp->meters = kmalloc_array(METER_HASH_BUCKETS,
 588                                    sizeof(struct hlist_head), GFP_KERNEL);
 589
 590         if (!dp->meters)
 591                 return -ENOMEM;
 592
 593         for (i = 0; i < METER_HASH_BUCKETS; i++)
 594                 INIT_HLIST_HEAD(&dp->meters[i]);
 595
 596         return 0;
 597 }
 598
 599 void ovs_meters_exit(struct datapath *dp)
 600 {
 601         int i;
 602
 603         for (i = 0; i < METER_HASH_BUCKETS; i++) {
 604                 struct hlist_head *head = &dp->meters[i];
 605                 struct dp_meter *meter;
 606                 struct hlist_node *n;
 607
 608                 hlist_for_each_entry_safe(meter, n, head, dp_hash_node)
 609                         kfree(meter);
 610         }
 611
 612         kfree(dp->meters);
 613 }