int ldb_kv_modify_internal(struct ldb_module *module,
			   const struct ldb_message *msg,
			   struct ldb_request *req)
{
	struct ldb_context *ldb = ldb_module_get_ctx(module);
	void *data = ldb_module_get_private(module);
	struct ldb_kv_private *ldb_kv =
	    talloc_get_type(data, struct ldb_kv_private);
	struct ldb_message *msg2;
	unsigned int i, j;
	int ret = LDB_SUCCESS, idx;
	struct ldb_control *control_permissive = NULL;
	TALLOC_CTX *mem_ctx = talloc_new(req);

	if (mem_ctx == NULL) {
		return ldb_module_oom(module);
	}

	if (req) {
		control_permissive = ldb_request_get_control(req,
					LDB_CONTROL_PERMISSIVE_MODIFY_OID);
	}

	msg2 = ldb_msg_new(mem_ctx);
	if (msg2 == NULL) {
		ret = LDB_ERR_OTHER;
		goto done;
	}

	ret = ldb_kv_search_dn1(
	    module, msg->dn, msg2, LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC);
	if (ret != LDB_SUCCESS) {
		goto done;
	}

	for (i=0; i<msg->num_elements; i++) {
		struct ldb_message_element *el = &msg->elements[i], *el2;
		struct ldb_val *vals;
		const struct ldb_schema_attribute *a = ldb_schema_attribute_by_name(ldb, el->name);
		const char *dn;
		uint32_t options = 0;
		if (control_permissive != NULL) {
			options |= LDB_MSG_FIND_COMMON_REMOVE_DUPLICATES;
		}

		switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
		case LDB_FLAG_MOD_ADD:

			if (el->num_values == 0) {
				ldb_asprintf_errstring(ldb,
						       "attribute '%s': attribute on '%s' specified, but with 0 values (illegal)",
						       el->name, ldb_dn_get_linearized(msg2->dn));
				ret = LDB_ERR_CONSTRAINT_VIOLATION;
				goto done;
			}

			/* make a copy of the array so that a permissive
			 * control can remove duplicates without changing the
			 * original values, but do not copy data as we do not
			 * need to keep it around once the operation is
			 * finished */
			if (control_permissive) {
				el = talloc(msg2, struct ldb_message_element);
				if (!el) {
					ret = LDB_ERR_OTHER;
					goto done;
				}
				*el = msg->elements[i];
				el->values = talloc_array(el, struct ldb_val, el->num_values);
				if (el->values == NULL) {
					ret = LDB_ERR_OTHER;
					goto done;
				}
				for (j = 0; j < el->num_values; j++) {
					el->values[j] = msg->elements[i].values[j];
				}
			}

			if (el->num_values > 1 && ldb_kv_single_valued(a, el)) {
				ldb_asprintf_errstring(ldb, "SINGLE-VALUE attribute %s on %s specified more than once",
						       el->name, ldb_dn_get_linearized(msg2->dn));
				ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
				goto done;
			}

			/* Checks if element already exists */
			idx = ldb_kv_find_element(msg2, el->name);
			if (idx == -1) {
				if (ldb_kv_msg_add_element(msg2, el) != 0) {
					ret = LDB_ERR_OTHER;
					goto done;
				}
				ret = ldb_kv_index_add_element(
				    module, ldb_kv, msg2, el);
				if (ret != LDB_SUCCESS) {
					goto done;
				}
			} else {
				j = (unsigned int) idx;
				el2 = &(msg2->elements[j]);

				/* We cannot add another value on a existing one
				   if the attribute is single-valued */
				if (ldb_kv_single_valued(a, el)) {
					ldb_asprintf_errstring(ldb, "SINGLE-VALUE attribute %s on %s specified more than once",
						               el->name, ldb_dn_get_linearized(msg2->dn));
					ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
					goto done;
				}

				/* Check that values don't exist yet on multi-
				   valued attributes or aren't provided twice */
				if (!(el->flags &
				      LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK)) {
					struct ldb_val *duplicate = NULL;
					ret = ldb_msg_find_common_values(ldb,
									 msg2,
									 el,
									 el2,
									 options);

					if (ret ==
					    LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS) {
						ldb_asprintf_errstring(ldb,
							"attribute '%s': value "
							"#%u on '%s' already "
							"exists", el->name, j,
							ldb_dn_get_linearized(msg2->dn));
						goto done;
					} else if (ret != LDB_SUCCESS) {
						goto done;
					}

					ret = ldb_msg_find_duplicate_val(
						ldb, msg2, el, &duplicate, 0);
					if (ret != LDB_SUCCESS) {
						goto done;
					}
					if (duplicate != NULL) {
						ldb_asprintf_errstring(
							ldb,
							"attribute '%s': value "
							"'%.*s' on '%s' "
							"provided more than "
							"once in ADD",
							el->name,
							(int)duplicate->length,
							duplicate->data,
							ldb_dn_get_linearized(msg->dn));
						ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
						goto done;
					}
				}

				/* Now combine existing and new values to a new
				   attribute record */
				vals = talloc_realloc(msg2->elements,
						      el2->values, struct ldb_val,
						      el2->num_values + el->num_values);
				if (vals == NULL) {
					ldb_oom(ldb);
					ret = LDB_ERR_OTHER;
					goto done;
				}

				for (j=0; j<el->num_values; j++) {
					vals[el2->num_values + j] =
						ldb_val_dup(vals, &el->values[j]);
				}

				el2->values = vals;
				el2->num_values += el->num_values;

				ret = ldb_kv_index_add_element(
				    module, ldb_kv, msg2, el);
				if (ret != LDB_SUCCESS) {
					goto done;
				}
			}

			break;

		case LDB_FLAG_MOD_REPLACE:

			if (el->num_values > 1 && ldb_kv_single_valued(a, el)) {
				ldb_asprintf_errstring(ldb, "SINGLE-VALUE attribute %s on %s specified more than once",
						       el->name, ldb_dn_get_linearized(msg2->dn));
				ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
				goto done;
			}

			/*
			 * We don't need to check this if we have been
			 * pre-screened by the repl_meta_data module
			 * in Samba, or someone else who can claim to
			 * know what they are doing.
			 */
			if (!(el->flags & LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK)) {
				struct ldb_val *duplicate = NULL;

				ret = ldb_msg_find_duplicate_val(ldb, msg2, el,
								 &duplicate, 0);
				if (ret != LDB_SUCCESS) {
					goto done;
				}
				if (duplicate != NULL) {
					ldb_asprintf_errstring(
						ldb,
						"attribute '%s': value '%.*s' "
						"on '%s' provided more than "
						"once in REPLACE",
						el->name,
						(int)duplicate->length,
						duplicate->data,
						ldb_dn_get_linearized(msg2->dn));
					ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
					goto done;
				}
			}

			/* Checks if element already exists */
			idx = ldb_kv_find_element(msg2, el->name);
			if (idx != -1) {
				j = (unsigned int) idx;
				el2 = &(msg2->elements[j]);

				/* we consider two elements to be
				 * equal only if the order
				 * matches. This allows dbcheck to
				 * fix the ordering on attributes
				 * where order matters, such as
				 * objectClass
				 */
				if (ldb_msg_element_equal_ordered(el, el2)) {
					continue;
				}

				/* Delete the attribute if it exists in the DB */
				if (ldb_kv_msg_delete_attribute(
					module, ldb_kv, msg2, el->name) != 0) {
					ret = LDB_ERR_OTHER;
					goto done;
				}
			}

			/* Recreate it with the new values */
			if (ldb_kv_msg_add_element(msg2, el) != 0) {
				ret = LDB_ERR_OTHER;
				goto done;
			}

			ret =
			    ldb_kv_index_add_element(module, ldb_kv, msg2, el);
			if (ret != LDB_SUCCESS) {
				goto done;
			}

			break;

		case LDB_FLAG_MOD_DELETE:
			dn = ldb_dn_get_linearized(msg2->dn);
			if (dn == NULL) {
				ret = LDB_ERR_OTHER;
				goto done;
			}

			if (msg->elements[i].num_values == 0) {
				/* Delete the whole attribute */
				ret = ldb_kv_msg_delete_attribute(
				    module,
				    ldb_kv,
				    msg2,
				    msg->elements[i].name);
				if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE &&
				    control_permissive) {
					ret = LDB_SUCCESS;
				} else {
					ldb_asprintf_errstring(ldb,
							       "attribute '%s': no such attribute for delete on '%s'",
							       msg->elements[i].name, dn);
				}
				if (ret != LDB_SUCCESS) {
					goto done;
				}
			} else {
				/* Delete specified values from an attribute */
				for (j=0; j < msg->elements[i].num_values; j++) {
					ret = ldb_kv_msg_delete_element(
					    module,
					    ldb_kv,
					    msg2,
					    msg->elements[i].name,
					    &msg->elements[i].values[j]);
					if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE &&
					    control_permissive) {
						ret = LDB_SUCCESS;
					} else if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
						ldb_asprintf_errstring(ldb,
								       "attribute '%s': no matching attribute value while deleting attribute on '%s'",
								       msg->elements[i].name, dn);
					}
					if (ret != LDB_SUCCESS) {
						goto done;
					}
				}
			}
			break;
		default:
			ldb_asprintf_errstring(ldb,
					       "attribute '%s': invalid modify flags on '%s': 0x%x",
					       msg->elements[i].name, ldb_dn_get_linearized(msg->dn),
					       msg->elements[i].flags & LDB_FLAG_MOD_MASK);
			ret = LDB_ERR_PROTOCOL_ERROR;
			goto done;
		}
	}

	ret = ldb_kv_store(module, msg2, TDB_MODIFY);
	if (ret != LDB_SUCCESS) {
		goto done;
	}

	ret = ldb_kv_modified(module, msg2->dn);
	if (ret != LDB_SUCCESS) {
		goto done;
	}

done:
	TALLOC_FREE(mem_ctx);
	return ret;
}