text: /*
   * fatcache - memcache on ssd.
   * Copyright (C) 2013 Twitter, Inc.
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  #include <ctype.h>
  
  #include <fc_core.h>
  #include <fc_memcache.h>
  
  /*
   * From memcache protocol specification:
   *
   * Data stored by memcached is identified with the help of a key. A key
   * is a text string which should uniquely identify the data for clients
   * that are interested in storing and retrieving it.  Currently the
   * length limit of a key is set at 250 characters (of course, normally
   * clients wouldn't need to use such long keys); the key must not include
   * control characters or whitespace.
   */
  #define MEMCACHE_MAX_KEY_LENGTH 250
  
  /*
   * Return true, if the memcache command is a storage command, otherwise
   * return false
   */
  static bool
  memcache_storage(struct msg *r)
  {
      switch (r->type) {
      case MSG_REQ_SET:
      case MSG_REQ_CAS:
      case MSG_REQ_ADD:
      case MSG_REQ_REPLACE:
      case MSG_REQ_APPEND:
      case MSG_REQ_PREPEND:
          return true;
  
      default:
          break;
      }
  
      return false;
  }
  
  /*
   * Return true, if the memcache command is a cas command, otherwise
   * return false
   */
  static bool
  memcache_cas(struct msg *r)
  {
      if (r->type == MSG_REQ_CAS) {
          return true;
      }
  
      return false;
  }
  
  /*
   * Return true, if the memcache command is a retrieval command, otherwise
   * return false
   */
  static bool
  memcache_retrieval(struct msg *r)
  {
      switch (r->type) {
      case MSG_REQ_GET:
      case MSG_REQ_GETS:
          return true;
  
      default:
          break;
      }
  
      return false;
  }
  
  /*
   * Return true, if the memcache command is a arithmetic command, otherwise
   * return false
   */
  static bool
  memcache_arithmetic(struct msg *r)
  {
      switch (r->type) {
      case MSG_REQ_INCR:
      case MSG_REQ_DECR:
          return true;
  
      default:
          break;
      }
  
      return false;
  }
  
  /*
   * Return true, if the memcache command is a delete command, otherwise
   * return false
   */
  static bool
  memcache_delete(struct msg *r)
  {
      if (r->type == MSG_REQ_DELETE) {
          return true;
      }
  
      return false;
  }
  
  /*
   * Return true, if the memcache command takes a key argument, otherwise
   * return false
   */
  static bool
  memcache_key(struct msg *r)
  {
      switch (r->type) {
      case MSG_REQ_GET:
      case MSG_REQ_GETS:
      case MSG_REQ_DELETE:
      case MSG_REQ_CAS:
      case MSG_REQ_SET:
      case MSG_REQ_ADD:
      case MSG_REQ_REPLACE:
      case MSG_REQ_APPEND:
      case MSG_REQ_PREPEND:
      case MSG_REQ_INCR:
      case MSG_REQ_DECR:
          return true;
  
      default:
          break;
      }
  
      return false;
  }
  
  /*
   * Return true, if the memcache command is a quit command, otherwise
   * return false
   */
  static bool
  memcache_quit(struct msg *r)
  {
      if (r->type == MSG_REQ_QUIT) {
          return true;
      }
  
      return false;
  }
  
  void
  memcache_parse_req(struct msg *r)
  {
      struct mbuf *b;
      uint8_t *p, *m;
      uint8_t ch;
      enum {
          SW_START,
          SW_REQ_TYPE,
          SW_SPACES_BEFORE_KEY,
          SW_KEY,
          SW_SPACES_BEFORE_KEYS,
          SW_SPACES_BEFORE_FLAGS,
          SW_FLAGS,
          SW_SPACES_BEFORE_EXPIRY,
          SW_EXPIRY,
          SW_SPACES_BEFORE_VLEN,
          SW_VLEN,
          SW_SPACES_BEFORE_CAS,
          SW_CAS,
          SW_RUNTO_VAL,
          SW_VAL,
          SW_SPACES_BEFORE_NUM,
          SW_NUM,
          SW_RUNTO_CRLF,
          SW_CRLF,
          SW_NOREPLY,
          SW_AFTER_NOREPLY,
          SW_ALMOST_DONE,
          SW_SENTINEL
      } state;
  
      state = r->state;
      b = STAILQ_LAST(&r->mhdr, mbuf, next);
  
      ASSERT(r->request);
      ASSERT(state >= SW_START && state < SW_SENTINEL);
      ASSERT(b != NULL);
      ASSERT(b->pos <= b->last);
  
      /* validate the parsing maker */
      ASSERT(r->pos != NULL);
      ASSERT(r->pos >= b->pos && r->pos <= b->last);
  
      for (p = r->pos; p < b->last; p++) {
          ch = *p;
  
          switch (state) {
  
          case SW_START:
              if (ch == ' ') {
                  break;
              }
  
              if (!islower(ch)) {
                  goto error;
              }
  
              /* req_start <- p; type_start <- p */
              r->token = p;
              state = SW_REQ_TYPE;
  
              break;
  
          case SW_REQ_TYPE:
              if (ch == ' ' || ch == CR) {
                  /* type_end = p - 1 */
                  m = r->token;
                  r->token = NULL;
                  r->type = MSG_UNKNOWN;
  
                  switch (p - m) {
  
                  case 3:
                      if (str4cmp(m, 'g', 'e', 't', ' ')) {
                          r->type = MSG_REQ_GET;
                          break;
                      }
  
                      if (str4cmp(m, 's', 'e', 't', ' ')) {
                          r->type = MSG_REQ_SET;
                          break;
                      }
  
                      if (str4cmp(m, 'a', 'd', 'd', ' ')) {
                          r->type = MSG_REQ_ADD;
                          break;
                      }
  
                      if (str4cmp(m, 'c', 'a', 's', ' ')) {
                          r->type = MSG_REQ_CAS;
                          break;
                      }
  
                      break;
  
                  case 4:
                      if (str4cmp(m, 'g', 'e', 't', 's')) {
                          r->type = MSG_REQ_GETS;
                          break;
                      }
  
                      if (str4cmp(m, 'i', 'n', 'c', 'r')) {
                          r->type = MSG_REQ_INCR;
                          break;
                      }
  
                      if (str4cmp(m, 'd', 'e', 'c', 'r')) {
                          r->type = MSG_REQ_DECR;
                          break;
                      }
  
                      if (str4cmp(m, 'q', 'u', 'i', 't')) {
                          r->type = MSG_REQ_QUIT;
                          r->quit = 1;
                          break;
                      }
  
                      break;
  
                  case 6:
                      if (str6cmp(m, 'a', 'p', 'p', 'e', 'n', 'd')) {
                          r->type = MSG_REQ_APPEND;
                          break;
                      }
  
                      if (str6cmp(m, 'd', 'e', 'l', 'e', 't', 'e')) {
                          r->type = MSG_REQ_DELETE;
                          break;
                      }
  
                      break;
  
                  case 7:
                      if (str7cmp(m, 'p', 'r', 'e', 'p', 'e', 'n', 'd')) {
                          r->type = MSG_REQ_PREPEND;
                          break;
                      }
  
                      if (str7cmp(m, 'r', 'e', 'p', 'l', 'a', 'c', 'e')) {
                          r->type = MSG_REQ_REPLACE;
                          break;
                      }
  
                      break;
                  }
  
                  if (memcache_key(r)) {
                      if (ch == CR) {
                          goto error;
                      }
                      state = SW_SPACES_BEFORE_KEY;
                  } else if (memcache_quit(r)) {
                      p = p - 1; /* go back by 1 byte */
                      state = SW_CRLF;
                  } else {
                      goto error;
                  }
              } else if (!islower(ch)) {
                  goto error;
              }
  
              break;
  
          case SW_SPACES_BEFORE_KEY:
              if (ch != ' ') {
                  p = p - 1; /* go back by 1 byte */
                  state = SW_KEY;
              }
  
              break;
  
          case SW_KEY:
              if (r->token == NULL) {
                  r->token = p;
                  r->key_start = p;
              }
  
              if (ch == ' ' || ch == CR) {
                  if ((p - r->key_start) > MEMCACHE_MAX_KEY_LENGTH) {
                      log_error("parsed bad req %"PRIu64" of type %d with key "
                                "prefix '%.*s...' and length %d that exceeds "
                                "maximum key length", r->id, r->type, 16,
                                r->key_start, p - r->key_start);
                      goto error;
                  }
                  r->key_end = p;
                  r->token = NULL;
  
                  /* get next state */
                  if (memcache_storage(r)) {
                      state = SW_SPACES_BEFORE_FLAGS;
                  } else if (memcache_arithmetic(r)) {
                      state = SW_SPACES_BEFORE_NUM;
                  } else if (memcache_delete(r)) {
                      state = SW_RUNTO_CRLF;
                  } else if (memcache_retrieval(r)) {
                      state = SW_SPACES_BEFORE_KEYS;
                  } else {
                      state = SW_RUNTO_CRLF;
                  }
  
                  if (ch == CR) {
                      if (memcache_storage(r) || memcache_arithmetic(r)) {
                          goto error;
                      }
                      p = p - 1; /* go back by 1 byte */
                  }
              }
  
              break;
  
          case SW_SPACES_BEFORE_KEYS:
              ASSERT(memcache_retrieval(r));
              switch (ch) {
              case ' ':
                  break;
  
              case CR:
                  state = SW_ALMOST_DONE;
                  break;
  
              default:
                  r->token = p;
                  goto fragment;
              }
  
              break;
  
          case SW_SPACES_BEFORE_FLAGS:
              if (ch != ' ') {
                  if (!isdigit(ch)) {
                      goto error;
                  }
                  p = p - 1; /* go back by 1 byte */
                  state = SW_FLAGS;
              }
  
              break;
  
          case SW_FLAGS:
              if (r->token == NULL) {
                  /* flags_start <- p */
                  r->token = p;
                  r->flags = 0;
              }
  
              if (isdigit(ch)) {
                  r->flags = r->flags * 10 + (uint32_t)(ch - '0');
              } else if (ch == ' ') {
                  /* flags_end <- p - 1 */
                  r->token = NULL;
                  state = SW_SPACES_BEFORE_EXPIRY;
              } else {
                  goto error;
              }
  
              break;
  
          case SW_SPACES_BEFORE_EXPIRY:
              if (ch != ' ') {
                  if (!isdigit(ch)) {
                      goto error;
                  }
                  p = p - 1; /* go back by 1 byte */
                  state = SW_EXPIRY;
              }
  
              break;
  
          case SW_EXPIRY:
              if (r->token == NULL) {
                  /* expiry_start <- p */
                  r->token = p;
                  r->expiry = 0;
              }
  
              if (isdigit(ch)) {
                  r->expiry = r->expiry * 10 + (uint32_t)(ch - '0');
              } else if (ch == ' ') {
                  /* expiry_end <- p - 1 */
                  r->token = NULL;
                  state = SW_SPACES_BEFORE_VLEN;
              } else {
                  goto error;
              }
  
              break;
  
          case SW_SPACES_BEFORE_VLEN:
              if (ch != ' ') {
                  if (!isdigit(ch)) {
                      goto error;
                  }
                  p = p - 1; /* go back by 1 byte */
                  state = SW_VLEN;
              }
  
              break;
  
          case SW_VLEN:
              if (r->token == NULL) {
                  /* vlen_start <- p */
                  r->token = p;
                  r->vlen = 0;
              }
  
              if (isdigit(ch)) {
                  r->vlen = r->vlen * 10 + (uint32_t)(ch - '0');
              } else if (memcache_cas(r)) {
                  if (ch != ' ') {
                      goto error;
                  }
                  /* vlen_end <- p - 1 */
                  r->rvlen = r->vlen;
                  p = p - 1; /* go back by 1 byte */
                  r->token = NULL;
                  state = SW_SPACES_BEFORE_CAS;
              } else if (ch == ' ' || ch == CR) {
                  /* vlen_end <- p - 1 */
                  r->rvlen = r->vlen;
                  p = p - 1; /* go back by 1 byte */
                  r->token = NULL;
                  state = SW_RUNTO_CRLF;
              } else {
                  goto error;
              }
  
              break;
  
          case SW_SPACES_BEFORE_CAS:
              if (ch != ' ') {
                  if (!isdigit(ch)) {
                      goto error;
                  }
                  p = p - 1; /* go back by 1 byte */
                  state = SW_CAS;
              }
  
              break;
  
          case SW_CAS:
              if (r->token == NULL) {
                  /* cas_start <- p */
                  r->token = p;
                  r->cas = 0;
              }
  
              if (isdigit(ch)) {
                  r->cas = r->cas * 10ULL + (uint64_t)(ch - '0');
              } else if (ch == ' ' || ch == CR) {
                  /* cas_end <- p - 1 */
                  p = p - 1; /* go back by 1 byte */
                  r->token = NULL;
                  state = SW_RUNTO_CRLF;
              } else {
                  goto error;
              }
  
              break;
  
          case SW_RUNTO_VAL:
              switch (ch) {
              case LF:
                  /* val_start <- p + 1 */
                  state = SW_VAL;
                  break;
  
              default:
                  goto error;
              }
  
              break;
  
          case SW_VAL:
              if (r->value == NULL) {
                  r->value = p;
              }
              m = p + r->rvlen;
              if (m >= b->last) {
                  ASSERT(r->rvlen >= (uint32_t)(b->last - p));
                  r->rvlen -= (uint32_t)(b->last - p);
                  m = b->last - 1;
                  p = m; /* move forward by vlen bytes */
                  break;
              }
              switch (*m) {
              case CR:
                  /* val_end <- p - 1 */
                  p = m; /* move forward by vlen bytes */
                  state = SW_ALMOST_DONE;
                  break;
  
              default:
                  goto error;
              }
  
              break;
  
          case SW_SPACES_BEFORE_NUM:
              if (ch != ' ') {
                  if (!isdigit(ch)) {
                      goto error;
                  }
                  p = p - 1; /* go back by 1 byte */
                  state = SW_NUM;
              }
  
              break;
  
          case SW_NUM:
              if (r->token == NULL) {
                  /* num_start <- p */
                  r->token = p;
                  r->num = 0;
              }
  
              if (isdigit(ch)) {
                  r->num = r->num * 10ULL + (uint64_t)(ch - '0');
              } else if (ch == ' ' || ch == CR) {
                  r->token = NULL;
                  /* num_end <- p - 1 */
                  p = p - 1; /* go back by 1 byte */
                  state = SW_RUNTO_CRLF;
              } else {
                  goto error;
              }
  
              break;
  
          case SW_RUNTO_CRLF:
              switch (ch) {
              case ' ':
                  break;
  
              case 'n':
                  if (memcache_storage(r) || memcache_arithmetic(r) || memcache_delete(r)) {
                      p = p - 1; /* go back by 1 byte */
                      state = SW_NOREPLY;
                  } else {
                      goto error;
                  }
  
                  break;
  
              case CR:
                  if (memcache_storage(r)) {
                      state = SW_RUNTO_VAL;
                  } else {
                      state = SW_ALMOST_DONE;
                  }
  
                  break;
  
              default:
                  goto error;
              }
  
              break;
  
          case SW_NOREPLY:
              if (r->token == NULL) {
                  /* noreply_start <- p */
                  r->token = p;
              }
  
              switch (ch) {
              case ' ':
              case CR:
                  m = r->token;
                  if (((p - m) == 7) && str7cmp(m, 'n', 'o', 'r', 'e', 'p', 'l', 'y')) {
                      ASSERT(memcache_storage(r) || memcache_arithmetic(r) || memcache_delete(r));
                      r->token = NULL;
                      /* noreply_end <- p - 1 */
                      r->noreply = 1;
                      state = SW_AFTER_NOREPLY;
                      p = p - 1; /* go back by 1 byte */
                  } else {
                      goto error;
                  }
              }
  
              break;
  
          case SW_AFTER_NOREPLY:
              switch (ch) {
              case ' ':
                  break;
  
              case CR:
                  if (memcache_storage(r)) {
                      state = SW_RUNTO_VAL;
                  } else {
                      state = SW_ALMOST_DONE;
                  }
                  break;
  
              default:
                  goto error;
              }
  
              break;
  
          case SW_CRLF:
              switch (ch) {
              case ' ':
                  break;
  
              case CR:
                  state = SW_ALMOST_DONE;
                  break;
  
              default:
                  goto error;
              }
  
              break;
  
          case SW_ALMOST_DONE:
              switch (ch) {
              case LF:
                  /* req_end <- p */
                  goto done;
  
              default:
                  goto error;
              }
  
              break;
  
          case SW_SENTINEL:
          default:
              NOT_REACHED();
              break;
  
          }
      }
  
      /*
       * At this point, buffer from b->pos to b->last has been parsed completely
       * but we haven't been able to reach to any conclusion. Normally, this
       * means that we have to parse again starting from the state we are in
       * after more data has been read. The newly read data is either read into
       * a new mbuf, if existing mbuf is full (b->last == b->end) or into the
       * existing mbuf.
       *
       * The only exception to this is when the existing mbuf is full (b->last
       * is at b->end) and token marker is set, which means that we have to
       * copy the partial token into a new mbuf and parse again with more data
       * read into new mbuf.
       */
      ASSERT(p == b->last);
      r->pos = p;
      r->state = state;
  
      if (b->last == b->end && r->token != NULL) {
          r->pos = r->token;
          r->token = NULL;
          r->result = MSG_PARSE_REPAIR;
      } else {
          r->result = MSG_PARSE_AGAIN;
      }
  
      log_hexdump(LOG_VERB, b->pos, mbuf_length(b), "parsed req %"PRIu64" res %d "
                  "type %d state %d rpos %d of %d", r->id, r->result, r->type,
                  r->state, r->pos - b->pos, b->last - b->pos);
      return;
  
  fragment:
      ASSERT(p != b->last);
      ASSERT(r->token != NULL);
      r->pos = r->token;
      r->token = NULL;
      r->state = state;
      r->result = MSG_PARSE_FRAGMENT;
  
      log_hexdump(LOG_VERB, b->pos, mbuf_length(b), "parsed req %"PRIu64" res %d "
                  "type %d state %d rpos %d of %d", r->id, r->result, r->type,
                  r->state, r->pos - b->pos, b->last - b->pos);
      return;
  
  done:
      ASSERT(r->type > MSG_UNKNOWN && r->type < MSG_SENTINEL);
      r->pos = p + 1;
      ASSERT(r->pos <= b->last);
      r->state = SW_START;
      r->result = MSG_PARSE_OK;
  
      log_hexdump(LOG_VERB, b->pos, mbuf_length(b), "parsed req %"PRIu64" res %d "
                  "type %d state %d rpos %d of %d", r->id, r->result, r->type,
                  r->state, r->pos - b->pos, b->last - b->pos);
      return;
  
  error:
      r->result = MSG_PARSE_ERROR;
      r->state = state;
      errno = EINVAL;
  
      log_hexdump(LOG_INFO, b->pos, mbuf_length(b), "parsed bad req %"PRIu64" "
                  "res %d type %d state %d", r->id, r->result, r->type,
                  r->state);
  }
  
  /*
   * Pre-split copy handler invoked when the request is a multi vector -
   * 'get' or 'gets' request and is about to be split into two requests
   */
  void
  memcache_pre_splitcopy(struct mbuf *mbuf, void *arg)
  {
      struct msg *r = arg;                  /* request vector */
      struct string get = string("get ");   /* 'get ' string */
      struct string gets = string("gets "); /* 'gets ' string */
  
      ASSERT(r->request);
      ASSERT(mbuf_empty(mbuf));
  
      switch (r->type) {
      case MSG_REQ_GET:
          mbuf_copy(mbuf, get.data, get.len);
          break;
  
      case MSG_REQ_GETS:
          mbuf_copy(mbuf, gets.data, gets.len);
          break;
  
      default:
          NOT_REACHED();
      }
  }
  
  /*
   * Post-split copy handler invoked when the request is a multi vector -
   * 'get' or 'gets' request and has already been split into two requests
   */
  rstatus_t
  memcache_post_splitcopy(struct msg *r)
  {
      struct mbuf *mbuf;
      struct string crlf = string(CRLF);
  
      ASSERT(r->request);
      ASSERT(!STAILQ_EMPTY(&r->mhdr));
  
      mbuf = STAILQ_LAST(&r->mhdr, mbuf, next);
      mbuf_copy(mbuf, crlf.data, crlf.len);
  
      return FC_OK;
  }
  